Bicubic Nonhamiltonian Graph

A bicubic nonhamiltonian graph is a bicubic (i.e., bipartite cubic graph) that is nonhamiltonian (i.e., that does not possess a Hamiltonian cycle).

Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian, an assertion known as the Tutte bicubic graph conjecture. The Horton graph on 96 nodes, illustrated above, provided the first counterexample (Bondy and Murty 1976, p. 240).

Horton (1982) subsequently found a counterexample on 92 nodes, and two smaller (nonisomorphic) counterexamples on 78 nodes were found by Ellingham (1981, 1982b) and Owens (1983). Ellingham and Horton (1983) subsequently found a counterexample graph on 54 nodes and 81 edges. The smallest currently known counterexample is the 50-node Georges-Kelmans graph (Georges 1989; Grünbaum 2006, 2009).

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

	name	reference
50	Georges-Kelmans graph	Georges (1989), Grünbaum (2006, 2009)
54	54-Ellingham-Horton graph	Ellingham and Horton (1983)
78	78-Ellingham-Horton graph	Ellingham (1981, 1982)
78	78-Owens graph	Owens (1983)
92	92-Horton graph	Horton (1982)
96	96-Horton graph	Bondy and Murty (1976)