The combinatorial structure of a ddimensional simple convex
polytope  as given, for example, by the set of the (d1)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 dpolytope are exactly all
the (d1)regular, connected, induced, nonseparating
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
2complex without a free edge, and without 2dimensional
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
4dimensional counterexamples to Perles' conjecture.
