Editing Tait's conjecture (section)

{{about|graph theory|the conjectures in knot theory|Tait conjectures}}
{{short description|Disproven graph theory}}
In mathematics, '''Tait's conjecture''' states that "Every [[K-vertex-connected graph|3-connected]] [[Planar graph|planar]] [[cubic graph]] has a [[Hamiltonian cycle]] (along the edges) through all its [[Vertex (geometry)|vertices]]". It was proposed by {{harvs|first=P. G.|last=Tait|authorlink=P. G. Tait|year=1884|txt}} and disproved by {{harvs|first=W. T.|last=Tutte|authorlink=W. T. Tutte|year=1946|txt}}, 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 {{harvtxt|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.

The conjecture was significant, because if true, it would have implied the [[four color theorem]]: as Tait described, the four-color problem is equivalent to the problem of finding [[edge coloring|3-edge-colorings]] of [[bridgeless graph|bridgeless]] cubic planar graphs. In a Hamiltonian cubic planar graph, such an edge coloring is easy to find: use two colors alternately on the cycle, and a third color for all remaining edges. Alternatively, a 4-coloring of the faces of a Hamiltonian cubic planar graph may be constructed directly, using two colors for the faces inside the cycle and two more colors for the faces outside.