Tait's Hamiltonian graph conjecture asserted that every cubicpolyhedral 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.
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. B45, 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. Edinburgh10, 729,
1880.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable
Graphs." J. Comb. Th. B30, 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.