Home > 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.

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

1 Tutte's couterexample

1.1 Tutte's Fragment

The key to this counter-example is what is now known as Tutte's fragment, the following:-

If this fragment is part of a larger graph, then any Hamiltonian cycle through the graph MUST go in-or-out of the TOP vertex, (and either one of the lower ones). It cannot go in one lower vertex & out the other.

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

1.2 The counterexample

The fragment can then be used to construct the non-Hamiltonian polyhedron, by putting together 3 such fragments as follows...

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

A nice polyhedron, a tetrahedron (seen from above) with the bottom three corners similarly multiply-truncated, as shown by the fragment. In total it has 25 faces, 69 edges and 46 vertices.

Partly based on sci.math posting by Bill Taylor, used by permission