Tutte Conjecture
Tutte (1971/72) conjectured that there are no 3-connected nonhamiltonian bicubic graphs. However, a counterexample was found by J. D. Horton in 1976 (Gropp 1990), and several smaller counterexamples are now known.
NonhamiltonianBicubicGraphs
Known small counterexamples are summarized in the following table and illustrated above.
V name reference
50 Georges
graph Georges (1989), Grünbaum (2006, 2009)
54 Ellingham-Horton
54-graph Ellingham and Horton (1983)
78 Ellingham-Horton
78-graph Ellingham (1981, 1982)
78 Owens graph Owens (1983)
92 Horton
92-graph Horton (1982)
96 Horton 96-graph Bondy
and Murty (1976)
See also
Bicubic Graph, Bicubic Nonhamiltonian Graph, Cubic Graph, Ellingham-Horton Graphs, Georges Graph, Horton Graphs, Nonhamiltonian Graph, Tait's Hamiltonian Graph ConjectureExplore with Wolfram|Alpha
WolframAlpha
More things to try:
References
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 242, 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. "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, 1982.Ellingham, M. N. and Horton, J. D. "Non-Hamiltonian 3-Connected Cubic Bipartite Graphs." J. Combin. Th. Ser. B 34, 350-353, 1983.Georges, J. P. "Non-Hamiltonian Bicubic Graphs." J. Combin. Th. B 46, 121-124, 1989.Gropp, H. "Configurations and the Tutte Conjecture." Ars. Combin. A 29, 171-177, 1990.Grünbaum, B. "3-Connected Configurations (n_3) 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." Disc. 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." Disc. Math. 1, 203-208, 1971/72.Referenced on Wolfram|Alpha
Tutte ConjectureCite this as:
Weisstein, Eric W. "Tutte Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TutteConjecture.html