The combinatorial structure of a d-dimensional simple convex
polytope -- as given, for example, by the set of the (d-1)-regular
subgraphs of facets -- can be reconstructed from its abstract
graph [Blind & Mani 1988, Kalai 1988]. However, no
polynomial/efficient algorithm is known for this task, although a
polynomially checkable certificate for the correct reconstruction
exists [Kaibel & K\"orner 2000].
A much stronger certificate would be given by the following
characterization of the facet subgraphs, conjectured by M. Perles:
``The facet subgraphs of a simple d-polytope are
exactly all the (d-1)-regular, connected, induced,
non-separating subgraphs'' [Perles 1970].
We give examples for the validity of Perles conjecture:
In particular, it holds for the duals of cyclic polytopes,
and for the duals of stacked polytopes.
On the other hand, we observe that for any 4-dimensional
counterexample, the boundary of the (simplicial) dual polytope P*
contains a 2-complex without a free edge, and without 2-dimensional
homology. Examples of such complexes are known; we use a simple
modification of ``Bing's house'' (two walls removed) to construct
explicit 4-dimensional counterexamples to Perles' conjecture.