Tait's conjecture

From Wikipedia, the free encyclopedia

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.

[edit] Tutte's counterexample

[edit] 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 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 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 enough if common sense is applied.

[edit] The counterexample

The fragment can then be used to construct the non-Hamiltonian polyhedron, by putting together 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.)

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