Tait's conjecture

Tutte's fragment The key to this counter-example is what is now known as '''Tutte's fragment''', shown on the right. 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. The counterexample The fragment can then be used to construct the non-Hamiltonian Tutte graph, by putting together three such fragments as shown in the picture. The "compulsory" edges of the fragments, that must be part of any Hamiltonian path through the fragment, are connected at the central vertex; because any cycle can use only two of these three edges, there can be no Hamiltonian cycle. The resulting Tutte graph is 3-connected and planar, so by Steinitz' theorem it is the graph of a polyhedron. In total it has 25 faces, 69 edges and 46 vertices. It can be realized geometrically from a tetrahedron (the faces of which correspond to the four large faces in the drawing, three of which are between pairs of fragments and the fourth of which forms the exterior) by multiply truncating three of its vertices. Smaller counterexamples As show, there are exactly six 38-vertex non-Hamiltonian polyhedra that have nontrivial three-edge cuts. They are formed by replacing two of the vertices of a pentagonal prism by the same fragment used in Tutte's example. == See also ==