The Georges-Kelmans graph, also called the Georges graph, is the 50-vertex bicubic nonhamiltonian graph illustrated
above, with cyclic edge connectivity at
least 4. The graph was originally constructed by Kel'mans
(1988), though rediscovered independently by Georges (1989) as the smallest member
of an infinite family of bicubic
nonhamiltonian graphs that are k-connected
with 
.
Gropp (1990, 1993) subsequently stated that the two graphs
are isomorphic, and Kel'mans (1994) later gave
a fuller account of his construction. Grünbaum (2009, p. 317) regarded
the identification as unjustified from the published accounts, but the direct reconstruction
given below confirms the graph isomorphism.
Brinkmann et al. (2022) adopted the combined name Georges-Kelmans graph, credited
Kel'mans and Georges with independent discovery, and proved that the graph
is the smallest bicubic nonhamiltonian
graph that is k-connected with 
. Bondy and Murty (2008, p. 483)
call it the Kelmans-Georges graph.
The construction from two copies of a modification of the 18-vertex member of the Ellingham-Horton graphs is illustrated above (Grünbaum 2006; Grünbaum 2009, pp. 310-311).
The Georges-Kelmans graph has girth 6 and is the Levi graph of the 
Georges configuration, for which Grünbaum
(2009, pp. 311-316) gave a geometric realization
and Kocay (2010) subsequently gave a geometric
realization with exact rational homogeneous
coordinates.
The Georges-Kelmans graph has graph crossing number 12.
Kel'mans's two basic operations are shown above, reproducing his Figures 1 and 2. Given a bicubic graph 
and two distinct edges 
and 
, the operation 
replaces each selected graph
edge by a three-edge graph
path and attaches a pendant edge to each of the
two new internal vertices. The result is a graph
multipole 
with four poles, represented here by vertices of
vertex degree 1. The second operation deletes two
specified edges 
and 
from the Petersen graph
and replaces them by graph multipoles 
and 
with four poles each, attached as shown, to form the bicubic graph 
.
Let 
be the multigraph on two vertices
with three parallel edges 
, 
, and 
, and let 
, with 
designated the middle graph edge.
Form 
from two copies of 
whose middle edges are denoted
and 
,
and then set 
.
Finally, form 
,
where 
and 
are two copies of 
. This gives Kel'mans's 50-vertex graph 
.
The graph 
is illustrated above, with the two copies of 
shown in blue and green and the six remaining vertices
of the Petersen framework shown in orange. Direct computation shows that 
is isomorphic to the
Georges-Kelmans graph.
The three panels above redraw Figure 18.12 of Bondy and Murty (2008, p. 483). They present this construction in terms of a Petersen
graph and an intermediate 18-vertex bicubic
graph 
.
Their Figure 18.12b shows 
in a Petersen-like drawing, while Figure 18.12c redraws
the same graph to make the substitution clearer. In the
notation above, 
,
and their marked edges 
and 
are the middle edges 
and 
of the two copies of 
. A Hamiltonian cycle
in 
containing both 
and 
would reduce to a Hamiltonian cycle in the Petersen graph, which is impossible. The restriction
is on using both marked edges, not on the existence
of a Hamiltonian cycle in 
itself.
The final step substitutes two copies of the redrawn 
into the Petersen graph
using the two marked edges as attachment sites. Each
marked edge is subdivided
twice, and the four new vertices are attached to
the remaining Petersen framework as in the operation 
above. Each copy thus contributes 22 vertices,
while the framework contributes six, giving 50 vertices
in all.
To see why the resulting graph is a nonhamiltonian graph, suppose it had a Hamiltonian cycle.
The Hamiltonian cycle would use either two or
four attachment edges at each substituted copy. If
it used two, they would have to belong to different marked edges.
If it used four, the two paths through the copy would
have to pair the attachment vertices on each marked
edge separately. Otherwise, restoring the marked edges would produce a Hamiltonian
cycle in 
through both 
and 
.
The permitted traversals can therefore be replaced by traversals through the two
removed Petersen vertices, giving a Hamiltonian
cycle in the Petersen graph and hence a contradiction (Bondy and Murty 2008, Exercise 18.2.5).
It is implemented in the Wolfram Language as GraphData["GeorgesGraph"].
with No Hamiltonian Circuit." Bull. Inst. Combin.
Appl. 46, 15-26, 2006.Grünbaum, B.