Tait's Hamiltonian Graph Conjecture

The conjecture that every cubic polyhedral graph is Hamiltonian. It was proposed by Tait in 1880 and refuted by Tutte (1946) with the 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 examples known has 38 vertices (Lederberg 1965), 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)

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.

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.

Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.