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.
Tutte's counterexample
Tutte's fragment
TutteFrag.png
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 & 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.
The counterexample
PlanarNonHamil.png
The fragment can then be used to construct the non-Hamiltonian polyhedron, by putting together 3 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 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 (http://www.math.niu.edu/%7Erusin/known-math/97/tutte), used by permission