Hamiltonicity of graphs of convex polytopes

Problem: Are all simple 4-polytopes Hamiltonian?

The statement of this problem is taken from the title of an article by Moshe Rosenfeld [3] who constructed extensive family of nonhamiltonian 4-regular 4-connected graphs (none of which is 4-polytopal). David Barnette (see [2], p. 1145) conjectured that the answer to this question is positive. There are no obvious reasons that would support this conjecture except that no counterexamples are known.

On the other hand, a simpler statement that every simple 3-polytope (alias cubic 3-connected planar graph) is Hamiltonian was conjectured by Tait and disproved only half a century later by Tutte. This supports me to make the following:

Conjecture: For every integer d  that is greater or equal to 3, there exists a simple d-polytope whose graph is not Hamiltonian.

A related question is the following:

Problem: Is there an integer k such that every k-connected 4-polytopal graph is Hamiltonian?

Note that in contrast to 3-polytopal graphs which cannot be 6-connected, 4-polytopal graphs with arbitrarily large connectivity exist [1].



[1] B. Grünbaum, Convex polytopes, Wiley-Interscience, 1967.

[2] B. Grünbaum, Polytopes, graphs, and complexes, Bull. AMS 76 (1970) 1131-1201.

[3] M. Rosenfeld, Are all simple 4-polytopes Hamiltonian?, Israel J. Math. 46 (1983) 161-169.

Send comments to Bojan.Mohar@uni-lj.si

Revised: oktober 24, 2001.