TOPICS
Search

Tait's Hamiltonian Graph Conjecture

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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.

TaitsHamiltonianGraphConjecture

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.

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

See also

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

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

Subject classifications