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]