Tait's conjecture

In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices".

It was proposed by P. G. Tait (1884) and disproved by W. T. Tutte (1946), who constructed a counterexample with 25 faces, 69 edges and 46 vertices.

Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988).

The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.

As Holton & McKay (1988) show, there are exactly six 38-vertex non-Hamiltonian polyhedra that have nontrivial three-edge cuts.