TOPICS

# Tait's Hamiltonian Graph Conjecture

Tait's Hamiltonian graph conjecture asserted that every cubic polyhedral graph is Hamiltonian. It was proposed by Tait in 1880 and refuted by Tutte (1946) with a counterexample on 46 vertices (Lederberg 1965) now known as Tutte's graph. Had the conjecture been true, it would have implied the four-color theorem.

The following table summarizes some named counterexamples, illustrated above. The smallest example with 38 vertices (the Barnette-Bośak-Lederberg graph; e.g., Lederberg 1965), was proved minimal by Holton and McKay (Holton and McKay 1988, van Cleemput and Zamfirescu 2018), and was apparently also discovered by D. Barnette and J. Bosák around the same time.

 graph reference 38 Barnette-Bośak-Lederberg graph Lederberg (1965), Thomassen (1981), Grünbaum (2003, Fig. 17.1.5) 42 Faulkner-Younger graph 42 Faulkner and Younger (1974) 42 Grinberg graph 42 Faulkner and Younger (1974) 44 Faulkner-Younger graph 44 Faulkner and Younger (1974) 44 Grinberg graph 44 Sachs (1968), Berge (1973), Read and Wilson (1998, p. 274) 46 Grinberg graph 46 Bondy and Murty (1976, p. 162) 46 Tutte's graph Tutte (1972), Bondy and Murty (1976, p. 161) 94 Thomassen graph 94 Thomassen (1981) 124 124-Grünbaum graph 124 Zamfirescu (1976)

Barnette-Bosák-Lederberg Graph, Connected Graph, Cubic Graph, Four-Color Theorem, Graph Vertex, Grinberg Graphs, Hamiltonian Cycle, Hamiltonian Graph, Tutte Conjecture, Tutte's Fragment, Tutte's Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Bondy, J. A. and Murty, U. S. R. Fig. 9.27 in Graph Theory with Applications. New York: North Holland, 1976.Faulkner, G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps." Discr. Math. 7, 67-74, 1974.Grünbaum, B. Fig. 17.1.5 in Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A. and McKay, B. D. "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." J. Combin. Th. SeR. B 45, 305-319, 1988.Honsberger, R. Mathematical Gems I. Washington, DC: Math. Assoc. Amer., pp. 82-89, 1973.Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.Pegg, E. Jr. "The Icosian Game, Revisited." Mathematica J. 310-314, 11, 2009.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 274, 1998.Sachs, H. "Ein von Kozyrev und Grinberg angegebener nicht-Hamiltonischer kubischer planarer Graph." In Beiträge zur Graphentheorie. pp. 127-130, 1968.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 198, 1990.Tait, P. G. "Remarks on the Colouring of Maps." Proc. Royal Soc. Edinburgh 10, 729, 1880.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.Tutte, W. T. "On Hamiltonian Circuits." J. London Math. Soc. 21, 98-101, 1946.Tutte, W. T. "Non-Hamiltonian Planar Maps." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 295-301, 1972.van Cleemput, N. and Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338 192-206, 2018.Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

## Cite this as:

Weisstein, Eric W. "Tait's Hamiltonian Graph Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TaitsHamiltonianGraphConjecture.html