Grünbaum–Nash-Williams conjecture

In graph theory, the Grünbaum–Nash-Williams conjecture states that every 4-vertex-connected toroidal graph has a Hamiltonian cycle.^[1] It is a generalization of Tutte's theorem on Hamiltonian cycles, according to which every 4-vertex-connected planar graph has a Hamiltonian cycle.^[2] An analogous theorem of Thomas and Yu holds for graphs on the projective plane.^[3]

For 4-vertex-connected planar and projective planar graphs, more strongly, every edge belongs to a Hamiltonian cycle. However, this stronger property is not true of toroidal graphs. For instance, the Cartesian product of two even cycles, with a diagonal added to one of its quadrilateral faces, is a 4-vertex-connected toroidal graph none of whose Hamiltonian cycles contains the added diagonal.^[4][5]

The conjecture was formulated in the early 1970s by Branko Grünbaum^[6] and Crispin Nash-Williams.^[7] As partial progress toward the conjecture, Robin Thomas and X. Yu proved that every 5-vertex-connected toroidal graph has a Hamiltonian cycle,^[8] and (with W. Zang) that every 4-vertex-connected toroidal graph has a Hamiltonian path.^[9]