Tutte's theorem on Hamiltonian cycles

In graph theory, a theorem of W. T. Tutte states that every 4-vertex-connected planar graph has a Hamiltonian cycle.^[1] It strengthens an earlier theorem of Hassler Whitney according to which every 4-vertex-connected maximal planar graph has a Hamiltonian cycle.^[2]

In turn, Tutte's theorem is strengthened by an analogous theorem of Robin Thomas and X. Yu for graphs on the projective plane,^[3] and by the unproven Grünbaum–Nash-Williams conjecture, according to which every 4-vertex-connected toroidal graph has a Hamiltonian cycle.^[4]

Tutte's theorem can be seen as a weakened version of Tait's conjecture on Hamiltonian cycles in 3-vertex-connected graphs, which was disproved by Tutte's discovery of the Tutte graph in 1946.^[5] Instead, Barnette's conjecture, still unproven, weakens Tait's conjecture in a different way, to bipartite planar graphs.^[6]

Tutte's original publication of the theorem in 1956 had a complicated proof; he included a simplification of the proof in a 1977 survey paper.^[7]