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.

Known small counterexamples are summarized in the following table and illustrated above.

	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)

---

REFERENCES

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 242, 1976.

Bondy, 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  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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength