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 couterexample

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.

The counterexample

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

                   ____
                  /\ F/\
                 /  \/  \         
                /   |    \           
               /    |     \          
              /    / \     \         
             /____/   \_____\
             \ F /     \  F /        
              \ /       \  /          
               v_________\/           

...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 (http://www.math.niu.edu/%7Erusin/known-math/97/tutte), used by permission

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.