## The minimality of the Georges–Kelmans graph

HTML articles powered by AMS MathViewer

- by
Gunnar Brinkmann, Jan Goedgebeur and Brendan D. McKay
**HTML**| PDF - Math. Comp.
**91**(2022), 1483-1500

## Abstract:

In 1971, Tutte wrote in an article that *it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian*. Motivated by this remark, Horton constructed a counterexample on $96$ vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts—even if they have girth 6—it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs.

In 1969 Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnette’s conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4.

## References

- R. E. L. Aldred, G. Brinkmann, and B. D. McKay,
*Announcement about Barnette’s conjecture*, 2000, https://www.fmf.uni-lj.si/~mohar/Problems/P4BarnetteConjecture.html. - D. Barnette,
*Conjecture 5. Recent progress in combinatorics*, Proceedings of the Third Waterloo Conference on Combinatorics, Academic Press, New York, 1969. - J. A. Bondy and U. S. R. Murty,
*Graph theory with applications*, American Elsevier Publishing Co., Inc., New York, 1976. MR**0411988**, DOI 10.1007/978-1-349-03521-2 - Gunnar Brinkmann,
*Fast generation of cubic graphs*, J. Graph Theory**23**(1996), no. 2, 139–149. MR**1408342**, DOI 10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.3.CO;2-1 - G. Brinkmann,
*A practical algorithm for the computation of the genus*, preprint arXiv:2005.08243, 2020. - Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, and Hadrien Mélot,
*House of Graphs: a database of interesting graphs*, Discrete Appl. Math.**161**(2013), no. 1-2, 311–314. MR**2973372**, DOI 10.1016/j.dam.2012.07.018 - G. Brinkmann, J. Goedgebeur, and B. D. McKay,
*Software archive for cubic bipartite non-hamiltonian graphs*, 2021, https://caagt.ugent.be/cubic-bip-nonham. - Gunnar Brinkmann and Brendan D. McKay,
*Fast generation of planar graphs*, MATCH Commun. Math. Comput. Chem.**58**(2007), no. 2, 323–357. MR**2357364** - Reinhard Diestel,
*Graph theory*, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR**2744811**, DOI 10.1007/978-3-642-14279-6 - M. N. Ellingham,
*Cycles in 3-connected cubic graphs*, Master’s thesis, University of Melbourne, 1982. - M. N. Ellingham and J. D. Horton,
*Non-Hamiltonian $3$-connected cubic bipartite graphs*, J. Combin. Theory Ser. B**34**(1983), no. 3, 350–353. MR**714456**, DOI 10.1016/0095-8956(83)90046-1 - John P. Georges,
*Non-Hamiltonian bicubic graphs*, J. Combin. Theory Ser. B**46**(1989), no. 1, 121–124. MR**982860**, DOI 10.1016/0095-8956(89)90012-9 - Roland Grund,
*Konstruktion schlichter Graphen mit gegebener Gradpartition*, Bayreuth. Math. Schr.**44**(1993), 73–104 (German, with German summary). MR**1224774** - D. A. Holton, B. Manvel, and B. D. McKay,
*Hamiltonian cycles in cubic $3$-connected bipartite planar graphs*, J. Combin. Theory Ser. B**38**(1985), no. 3, 279–297. MR**796604**, DOI 10.1016/0095-8956(85)90072-3 - D. A. Holton and B. D. McKay,
*The smallest non-Hamiltonian $3$-connected cubic planar graphs have $38$ vertices*, J. Combin. Theory Ser. B**45**(1988), no. 3, 305–319. MR**969251**, DOI 10.1016/0095-8956(88)90075-5 - J. D. Horton,
*On two-factors of bipartite regular graphs*, Discrete Math.**41**(1982), no. 1, 35–41. MR**676860**, DOI 10.1016/0012-365X(82)90079-6 - A. K. Kelmans,
*Cubic bipartite cyclically $4$-connected graphs with no Hamiltonian cycles*, Uspekhi Mat. Nauk**43**(1988), no. 3(261), 181–182 (Russian); English transl., Russian Math. Surveys**43**(1988), no. 3, 205–206. MR**955785**, DOI 10.1070/RM1988v043n03ABEH001738 - A. K. Kelmans, A. K. Kelmans, and A. K. Kelmans (eds.),
*Selected topics in discrete mathematics*, American Mathematical Society Translations, Series 2, vol. 158, American Mathematical Society, Providence, RI, 1994. Translated from the Russian by A. D. Vaĭnshteĭn; Translation edited by Simeon Ivanov. MR**1269122**, DOI 10.1090/trans2/158 - Kolja Knauer and Petru Valicov,
*Cuts in matchings of 3-connected cubic graphs*, European J. Combin.**76**(2019), 27–36. MR**3886509**, DOI 10.1016/j.ejc.2018.09.004 - William McCuaig,
*Edge reductions in cyclically $k$-connected cubic graphs*, J. Combin. Theory Ser. B**56**(1992), no. 1, 16–44. MR**1182455**, DOI 10.1016/0095-8956(92)90004-H - B. D. McKay and A. Piperno,
*Practical graph isomorphism, II*, J. Symbolic Comput.**60**(2014), 94–112, The latest version of the software is available at http://users.cecs.anu.edu.au/~bdm/nauty/. - Markus Meringer,
*Fast generation of regular graphs and construction of cages*, J. Graph Theory**30**(1999), no. 2, 137–146. MR**1665972**, DOI 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G - W. T. Tutte,
*On Hamiltonian circuits*, J. London Math. Soc.**21**(1946), 98–101. MR**19300**, DOI 10.1112/jlms/s1-21.2.98 - W. T. Tutte,
*On the $2$-factors of bicubic graphs*, Discrete Math.**1**(1971/72), no. 2, 203–208. MR**291010**, DOI 10.1016/0012-365X(71)90027-6 - N. C. Wormald,
*Models of random regular graphs*, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298. MR**1725006**

## Additional Information

**Gunnar Brinkmann**- Affiliation: Department of Applied Mathematics, Computer Science & Statistics, Ghent University, 9000 Ghent, Belgium
- MR Author ID: 252206
- Email: gunnar.brinkmann@ugent.be
**Jan Goedgebeur**- Affiliation: Department of Computer Science, KU Leuven Campus Kulak, 8500 Kortrijk, Belgium; Department of Applied Mathematics, Computer Science and Statistics, Ghent University, 9000 Ghent, Belgium; and Computer Science Department, University of Mons, 7000 Mons, Belgium
- MR Author ID: 945364
- ORCID: 0000-0001-8984-2463
- Email: jan.goedgebeur@kuleuven.be
**Brendan D. McKay**- Affiliation: Department of Computing, Australian National University, Canberra Australian Capitol Territory 2601, Australia
- MR Author ID: 122480
- Email: brendan.mckay@anu.edu.au
- Received by editor(s): March 17, 2021
- Received by editor(s) in revised form: August 31, 2021
- Published electronically: November 17, 2021
- Additional Notes: The second author was supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO). The third author was supported by a Francqui International Professorship.
- © Copyright 2021 by the authors
- Journal: Math. Comp.
**91**(2022), 1483-1500 - MSC (2020): Primary 05C45, 05C85, 05C10
- DOI: https://doi.org/10.1090/mcom/3701
- MathSciNet review: 4405503