Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian, an assertion known
as the Tutte conjecture. The Horton
graph on 96 nodes, illustrated above, provided the first counterexample (Bondy
and Murty 1976, p. 240).
Horton (1982) subsequently found a counterexample on 92 nodes, and two smaller (nonisomorphic) counterexamples on 78 nodes were found by Ellingham (1981, 1982b) and Owens (1983).
Ellingham and Horton (1983) subsequently found a counterexample graph on 54 nodes
and 81 edges. The smallest currently known counterexample is the 50-node Georges
graph (Georges 1989; Grünbaum 2006, 2009).
These small known counterexamples are summarized in the following table and illustrated above.
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 240, 1976.Bondy,
J. A. and Murty, U. S. R. Graph
Theory. Berlin: Springer-Verlag, pp. 487-488, 2008.Ellingham,
M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs." Research
Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.Ellingham,
M. N. Cycles in 3-Connected Cubics Graphs. M.Sc. thesis. Melbourne, Australia:
University of Melbourne, June 1982a.Ellingham, M. N. "Constructing
Certain Cubic Graphs." In Combinatorial Mathematics, IX: Proceedings of the
Ninth Australian Conference held at the University of Queensland, Brisbane, August
24-28, 1981 (Ed. E. J. Billington, S. Oates-Williams, and A. P. Street).
Berlin: Springer-Verlag, pp. 252-274, 1982b.Ellingham, M. N.
and Horton, J. D. "Non-Hamiltonian 3-Connected Cubic Bipartite Graphs."
J. Combin. Th. Ser. B34, 350-353, 1983.Georges, J. P.
"Non-Hamiltonian Bicubic Graphs." J. Combin. Th. B46, 121-124,
1989.Gropp, H. "Configurations and the Tutte Conjecture."
Ars. Combin. A29, 171-177, 1990.Grünbaum, B. "3-Connected
Configurations with No Hamiltonian Circuit." Bull. Inst. Combin.
Appl.46, 15-26, 2006.Grünbaum, B. Configurations
of Points and Lines. Providence, RI: Amer. Math. Soc., p. 311, 2009.Horton,
J. D. "On Two-Factors of Bipartite Regular Graphs." Discr. Math.41,
35-41, 1982.Owens, P. J. "Bipartite Cubic Graphs and a Shortness
Exponent." Disc. Math.44, 327-330, 1983.Tutte, W. T.
"On the 2-Factors of Bicubic Graphs." Discr. Math.1, 203-208,
1971.