This article is about graph theory. For the conjectures in knot theory, see Tait conjectures.
In mathematics, Tait's conjecture states that "Every 3-connectedplanarcubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by P. G. Tait (1884) and disproved by W. T. Tutte (1946), who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.
The conjecture was significant, because if true, it would have implied the four color theorem: as Tait described, the four-color problem is equivalent to the problem of finding 3-edge-colorings of bridgeless cubic planar graphs. In a Hamiltonian cubic planar graph, such an edge coloring is easy to find: use two colors alternately on the cycle, and a third color for all remaining edges. Alternatively, a 4-coloring of the faces of a Hamiltonian cubic planar graph may be constructed directly, using two colors for the faces inside the cycle and two more colors for the faces outside.
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 counterexampleedit
The fragment can then be used to construct the non-Hamiltonian Tutte graph, by putting together three such fragments as shown on 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 counterexamplesedit
As Holton & McKay (1988) 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 alsoedit
Grinberg's theorem, a necessary condition on the existence of a Hamiltonian cycle that can be used to show that a graph forms a counterexample to Tait's conjecture
^Barnette's conjecture, the Open Problem Garden, retrieved 2009-10-12.
Referencesedit
Holton, D. A.; McKay, B. D. (1988), "The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices", Journal of Combinatorial Theory, Series B, 45 (3): 305–319, doi:10.1016/0095-8956(88)90075-5.
Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series, 17: 30–46. Reprinted in Scientific Papers, Vol. II, pp. 85–98.
Tutte, W. T. (1946), "On Hamiltonian circuits" (PDF), Journal of the London Mathematical Society, 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98.
Partly based on sci.math posting by Bill Taylor, used by permission.
tait, conjecture, this, article, about, graph, theory, conjectures, knot, theory, tait, conjectures, mathematics, states, that, every, connected, planar, cubic, graph, hamiltonian, cycle, along, edges, through, vertices, proposed, tait, 1884, disproved, tutte,. This article is about graph theory For the conjectures in knot theory see Tait conjectures In mathematics Tait s conjecture states that Every 3 connected planar cubic graph has a Hamiltonian cycle along the edges through all its vertices It was proposed by P G Tait 1884 and disproved by W T Tutte 1946 who constructed a counterexample with 25 faces 69 edges and 46 vertices Several smaller counterexamples with 21 faces 57 edges and 38 vertices were later proved minimal by Holton amp McKay 1988 The condition that the graph be 3 regular is necessary due to polyhedra such as the rhombic dodecahedron which forms a bipartite graph with six degree four vertices on one side and eight degree three vertices on the other side because any Hamiltonian cycle would have to alternate between the two sides of the bipartition but they have unequal numbers of vertices the rhombic dodecahedron is not Hamiltonian The conjecture was significant because if true it would have implied the four color theorem as Tait described the four color problem is equivalent to the problem of finding 3 edge colorings of bridgeless cubic planar graphs In a Hamiltonian cubic planar graph such an edge coloring is easy to find use two colors alternately on the cycle and a third color for all remaining edges Alternatively a 4 coloring of the faces of a Hamiltonian cubic planar graph may be constructed directly using two colors for the faces inside the cycle and two more colors for the faces outside Contents 1 Tutte s counterexample 1 1 Tutte s fragment 1 2 The counterexample 1 3 Smaller counterexamples 2 See also 3 Notes 4 References 5 External linksTutte s counterexample edit nbsp Tutte s fragment edit 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 edit nbsp The fragment can then be used to construct the non Hamiltonian Tutte graph by putting together three such fragments as shown on 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 edit As Holton amp McKay 1988 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 editGrinberg s theorem a necessary condition on the existence of a Hamiltonian cycle that can be used to show that a graph forms a counterexample to Tait s conjecture Barnette s conjecture a still open refinement of Tait s conjecture stating that every bipartite cubic polyhedral graph is Hamiltonian 1 Notes edit Barnette s conjecture the Open Problem Garden retrieved 2009 10 12 References editHolton D A McKay B D 1988 The smallest non Hamiltonian 3 connected cubic planar graphs have 38 vertices Journal of Combinatorial Theory Series B 45 3 305 319 doi 10 1016 0095 8956 88 90075 5 Tait P G 1884 Listing s Topologie Philosophical Magazine 5th Series 17 30 46 Reprinted in Scientific Papers Vol II pp 85 98 Tutte W T 1946 On Hamiltonian circuits PDF Journal of the London Mathematical Society 21 2 98 101 doi 10 1112 jlms s1 21 2 98 Partly based on sci math posting by Bill Taylor used by permission External links editWeisstein Eric W Tait s Hamiltonian Graph Conjecture MathWorld Retrieved from https en wikipedia org w index php title Tait 27s conjecture amp oldid 1176274240, wikipedia, wiki, book, books, library,
