# Cubic bipartite non-hamiltonian graphs

CAAGT

Gunnar Brinkmann

Jan Goedgebeur

Brendan McKay

## Cubic bipartite non-hamiltonian graphs

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 the following article we show that there is no smaller counterexample:

• G. Brinkmann, J. Goedgebeur and B.D. McKay, The Minimality of the Georges-Kelmans Graph, 17 pages, 2021. Preprint: (arXiv).

This webpage contains the source code of the programs we used in our proof that there is no smaller non-hamiltonian 3-connected bipartite cubic graph than the Georges-Kelmans graph (which has 50 vertices).

Notes:
• Most of these programs were written specifically to prove the above result and are not intended to be used or adjusted to generate other kinds of graphs.
• The independent implementations are not optimised as they were only written to independently verify the results of the main programs up to reasonable orders.
• When we refer to certain Lemmas, Theorems or Figures in the description of the programs, the labels correspond to the labelling used in the arXiv-manuscript.

Programs:
• minibaum: Generator for cubic graps which we used to generate bipartite cubic graphs.
• genreg: Generator for regular graphs designed by Markus Meringer which Gunnar Brinkmann extended so it can also generate bipartite graphs efficiently. To use this extension, combine genreg_plus_bip.c and gendef.h with the original source files of genreg.
• cubhamg: Program which is part of the nauty package and which was used to search for hamiltonian cycles containing or avoiding certain edges.
• multi_hamiltonian-forbidden-edge.c: Program which tests if a given graph contains a forbidden edge (as defined in the proof of Lemma 2.2). The same test was also independently done using the program cubhamg which is part of the nauty package.
• multi_hamiltonian-forced-edge.c: Program which tests if a given graph contains a forced edge (as defined in the proof of Lemma 2.2). The same test was also also independently done using the program cubhamg which is part of the nauty package.
• test_type1_edge.c: Program which tests if a given graph contains a type 1 edge (as defined in the proof of Lemma 2.3). The same test was also independently done using the program cubhamg which is part of the nauty package.
• test_type2_edge.c: Program which tests if a given graph contains a type 2 edge (as defined in the proof of Lemma 2.3). The same test was also independently done using the program cubhamg which is part of the nauty package.
• multigraph.c: Program which was used to generate 5-pieces as defined in the proof of Lemma 2.4.
• make5pieces.c: Independent algorithm which was used in combination with minibaum to generate 5-pieces, thereby verifying the results of multigraph.c for 5-pieces up to 29 vertices.
• determine_class_of_5pieces.c: Program to determine the class of a 5-piece (cf. Lemma 2.4).
• minibaum-irred-8cycle.c: Modified version of minibaum which was adjusted to generate all irreducible bipartite cubic graphs of girth 6 (i.e. graphs which do not have an 8-cycle reduction from Figure 7) and which was used for part (a) of the proof of Theorem 1.1.
• is_reducible_tutte.c: Independently written filter to test if a given graph is irreducible. This filter was used in combination with the original version of minibaum to independently verify the results obtained by minibaum-irred-8cycle.c up to 40 vertices.
• xcubhamg6.c: Program which was used in combination with minibaum to generate all connected bipartite cubic graphs with at most 40 vertices that may be the reduction of a bipartite cubic graph of girth 6 (cf. part (b) of the proof of Theorem 1.1).
• 4tuples_are_extentable.c: Independently written filter to test if a given graph may be the reduction of a bipartite cubic graph of girth 6. This was used to independently verify the results obtained by xcubhamg6.c up to 34 vertices.
• plantri: Program which can be used to generate various types of planar graphs. This was used to generate 3-connected planar bipartite cubic graphs (cf. Theorem 4.1).
• multi_genus.c: Program which computes the genus of a graph.

Don't hesitate to contact us at jan.goedgebeur[at]ugent.be if you have any further questions or suggestions.

Last update: August 6, 2021.