TOPICS
Search

Tutte Bicubic Graph Conjecture

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Tutte bicubic graph conjecture asserted that there are no 3-connected bicubic nonhamiltonian graphs (Tutte 1971/72). 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.

Vnamereference
50Georges-Kelmans graphGeorges (1989), Grünbaum (2006, 2009)
54Ellingham-Horton 54-graphEllingham and Horton (1983)
78Ellingham-Horton 78-graphEllingham (1981, 1982)
78Owens graphOwens (1983)
92Horton 92-graphHorton (1982)
96Horton 96-graphBondy and Murty (1976)

See also

Bicubic Graph, Bicubic Nonhamiltonian Graph, Cubic Graph, Ellingham-Horton Graphs, Georges-Kelmans Graph, Horton Graphs, Nonhamiltonian Graph, Tait's Hamiltonian Graph Conjecture, Tutte Conjecture

Explore with Wolfram|Alpha

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, Germany: Springer-Verlag, pp. 487-488, 2008.Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs." Dept. of Math. Research Report No. 28. Melbourne, Australia: University of 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, Germany: 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. 29A, 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.

Cite this as:

Weisstein, Eric W. "Tutte Bicubic Graph Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TutteBicubicGraphConjecture.html

Subject classifications