Every 4-connected toroidal graph has a Hamilton cycle

Medium ★★ Graph Theory » Topological Graph Theory

Authors: Grunbaum, Branko, Nash-Williams, Crispin, St. J. A.— posted by fhavet on 2013-03-07

Status open high confidence

The Grunbaum-Nash-Williams conjecture that every 4-connected toroidal graph has a Hamilton cycle remains open. The strongest general results are still those cited in the OPG bibliography: Thomas and Yu (1997) settled the 5-connected case (and showed it is even Hamiltonian-connected), and Thomas, Yu, and Zang (2005) showed every 4-connected toroidal graph has a Hamilton path. Since 2013 the only directly relevant published progress is on special classes (e.g., 4-connected toroidal triangulations by Kawarabayashi-Ozeki, predating the post) and on the structure of Thomassen's edge-non-hamiltonian counterexamples (Ellingham-Marshall).

Cited literature (1)

partial Criticality of counterexamples to toroidal edge-hamiltonicity (2016)

M. N. Ellingham, Emily A. Marshall · Graphs and Combinatorics · arXiv:1312.1379 · doi:10.1007/s00373-015-1542-5

Investigates Thomassen-type 4-connected toroidal graphs containing edges not on any Hamilton cycle, showing certain generalizations are critical; this clarifies why an edge-Hamiltonicity inductive approach (the planar/projective-planar route) cannot work for the torus and bears on the structure any proof of the Grunbaum-Nash-Williams conjecture must respect.

Reviewer notes. The Kawarabayashi-Ozeki result that every 4-connected toroidal triangulation is Hamiltonian is widely cited but appears as a 2011 Eurocomb conference proceedings/preprint, predating the 2013-03-07 OPG posting; therefore not listed under since_posted. Several journal pages (SIAM, ScienceDirect, Springer link article) returned 403/redirect on direct fetch; the arXiv abstract for Ellingham-Marshall and the DOI registration confirm the 2013 submission and 2016 journal publication in Graphs and Combinatorics. No post-2013 arXiv preprint or journal paper announcing a full proof or refutation of the Grunbaum-Nash-Williams toroidal conjecture was found.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

Conjecture. Every 4-connected toroidal graph has a Hamilton cycle.

Discussion

Tutte [Tu] proved that every 4-connected planar graph has a Hamilton cycle. (See also [Th]). Thomas and Yu [TY] proved that every 4-connected projective-planar graph has a Hamilton cycle. Thomas and Yu [TY] also proved that every 5-connected toroidal graph has a Hamilton cycle. In fact, they show something stronger: every edge in a 5-connected toroidal graph is contained in a Hamilton cycle. This stronger result cannot be extended to 4-connected toroidal graphs: Thomassen [Th] showed 4-connected toroidal graphs in which certain edges are not contained in any Hamilton cycle.

Bibliography

★ [G] B. Grünbaum, Polytopes, graphs, and complexes. Bull. Amer. Math. Soc. 76 (1970) 1131-1201.
★ [N] C. St. J. A. Nash-Williams, Unexplored and semi-explored territories in graph theory. New Directions in Graph Theory, Academic Press, New York (1973) 169-176.
[TY] R. Thomas and X. Yu, 5-connected toroidal graphs are hamiltonian. J. Combinat. Theory Ser. B 69 (1997), no.1, 79-96.
[Th] C. Thomassen, A theorem on paths in planar graphs. J. Graph Theory 7 (1983) 169-176.
[Tu] W. T. Tutte, A theorem on planar graphs. Trans. Amer. Math. Soc. 82 (1956) 99-116.