  The combinatorial structure of a d-dimensional simple convex polytope can be
reconstructed from its abstract graph [Blind & Mani 1987, Kalai 1988]. However,
no polynomial/efficient algorithm is known for this task, although a
polynomially checkable certificate for the correct reconstruction was found by
[Joswig, Kaibel & Koerner 2000]. A much stronger certificate would be given by
the following characterization of the facet subgraphs, conjectured by M.
Perles:
  ``The facet subgraphs of the graph 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 identify a topological obstruction that must
be present in any counterexample to Perles' conjecture; thus, starting with a
modification of ``Bing's house'', we construct explicit 4-dimensional
counterexamples.
