**Hamilton Cycles in
Toroidal graphs**

Tutte [T] proved that every 4-connected toroidal graph has a
Hamiltonian cycle. He conjectured::

Conjecture: Every 4-connected toroidal graph is
Hamiltonian

I have also heard that this was independently conjectured by
Grunbaum. Thomas and Xu [TX] have shown that 5-connected toroidal
graphs are Hamiltonian.

A polyhedron P of genus g is formed by identifying
polyhedra face-to-face so that the resulting surface is of genus g. There are toroidal graphs that
cannot be realized as toroidal polyhedra [X].

Hence the following is strictly weaker than Conjecture 1.

Conjecture 2: Every 4-connected toroidal polyhedron is
Hamiltonian.

**References:**

[D] N. Dean, Open problems, Contemporary
Mathematics 147 (1993)
677-688

[TY] R. Thomas, X. Yu, Five-connected toroidal graphs are
Hamiltonian, J. Combin. Theory
Ser. B 69-1 (1997)
79--96

[T] W.T. Tutte, A theorem on planar graphs. Trans. Amer. Math. Soc. 82 (1956), 99--116.

[X] N.H. Xuong, Sur quelques
problems d'immersion d'un graphs dans une surface, These de
Doctorat d'Etat, Grenoble (1977)

Submitted by: Dan Archdeacon, Dept. of Math.
and Stat.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003