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].
References:
[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