Tait's conjecture

Tait's conjecture states that "Every polyhedron has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed in 1886 by P. G. Tait and disproved in 1946, when W. T. Tutte constructed a counterexample with 25 faces, 69 edges and 46 vertices. It has also been suggested for cubic graphs.

The conjecture could have been significant, because if true, it would have implied the four color theorem.

Tutte's counterexample

Tutte's fragment

The key to this counter-example is what is now known as "Tutte's fragment", see the picture.

If this fragment is part of a larger graph, then any Hamiltonian cyclethrough the graph must go in-or-out of the top vertex, (and either oneof the lower ones). It cannot go in one lower vertex and out the other.

Though this took some discovering, it is simple (if boring) to verify:-just sketch three such graphs and check out all the possibilities; three is enoughif common sense is applied.

The counterexample

The fragment can then be used to construct the non-Hamiltonian polyhedron, by puttingtogether three such fragments as shown on the picture.

These three fragments all have their "compulsory" vertex facing inwards; then it is easy to see there can be no Hamiltonian cycle. (The other six lines are just single edges, with 3 faces, and as usual another big face hidden underneath.)

Tutte's counterexample is a nice polyhedron, a tetrahedron (seen from above) with the bottom threecorners similarly multiply-truncated, as shown by the fragment.In total it has 25 faces, 69 edges and 46 vertices.

:"Partly based on [http://www.math.niu.edu/%7Erusin/known-math/97/tutte sci.math posting by Bill Taylor] , used by permission."