Call a graph "polyhedral" if it is simple, planar, and 3-connected. For example, the 1-dimensional skeleton of every 3-dimensional convex polytope, regarded as a graph, is polyhedral. By a theoreom of Steinitz, polyhedral graphs are exactly the graphs which appear as 1-skeleta of 3-dimensional convex polytopes.

Call a graph "Steinitzian" if it has a spanning polyhedral subgraph. ("Spanning" means that it has the same vertex set.) Where do Steinitzian graphs occur naturally? Is the 1-dimensional skeleton of every 4-dimensional polytope Steinitizian? Is every 1-skeleton of a $d$-tope with $d\geq 5$ Steinitzian?

I have checked a few easy polytopes. For example, it is not too much to check that the complete graph $K_5$ (the 1-skelton of the 4-dimensional simplex) is Steinitzian. Deleting one edge from $K_5$ reveals the graph of a bipyramid, so this is a spanning polyhedral subgraph. In fact, every complete graph $K_d$ with $d\geq 5$ is Steinitizan. It seems plausible that the 1-skeleton of every 4-tope may be Steinitzian, but it's not easy for me to see why and obviously I don't know a counterexample.

Knowing that a graph is Steinitizan means that one may visualize it by first constructing a 3-dimensional polytope and then connecting various interior edges (which might be interior to 2-dimensional faces). Notice that being Steinitzian is almost a higher-dimensional version of being hamiltonian, as we call a graph hamiltonian exactly when it has a spanning subgraph which is the 1-skeleton of a 2-dimensional convex polytope.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.