## 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].

**
****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

##### Revised: oktober 24, 2001.