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 & Korner 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,1984].

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 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 simple modifications of Borsuk's ``dunce hat'' (one wall removed) and of ``Bing's house'' (two walls removed) to construct explicit 4-dimensional counterexamples to Perles' conjecture.