Grinberg constructed a number of small cubic polyhedral graph that are counterexamples to Tait's Hamiltonian graph conjecture
(i.e., that every 3-connected cubic graph is Hamiltonian).
These nonhamiltonian graphs are all associated with Grinberg's name, with the 44-vertex
example being referred to as "Grinberg's graph" (Read and Wilson 1998,
p. 274) and the 46-vertex example as "the Grinberg graph" (Bondy and
Murty 1976, p. 162; Thomassen 1981). The 44-vertex graph is the smallest 3-valent,
planar, 3-connected, cyclically 5-connected nonhamiltonian graph (Grünbaum 1974).
As can be seen from the above figure, the 42-vertex graph can be derived from the 44-vertex graph simply by deletion of the single edge in the top middle part of the graph (Faulkner and Younger 1974). According to Zamfirescu (1976), the 44-vertex graph was discovered independently by Grinberg (1968) and Tutte (Grünbaum 1970, Faulkner and Younger 1974).
Additional embeddings for the 42- and 44-vertex Grinberg graphs are illustrated above.
Smaller 3-connected cubic nonhamiltonian graphs on 38 (the Barnette-Bosák-Lederberg graph) were subsequently found. The Faulkner-Younger
graphs are another pair of 3-connected cubic nonhamiltonian graphs on 42 and
44 vertices which, like the Grinberg graphs, are related to one another by deletion
of a single edge.
Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Bondy, J. A.
and Murty, U. S. R. Fig. 9.27 in Graph
Theory with Applications. New York: North Holland, p. 162, 1976.Faulkner,
G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps."
Discr. Math.7, 67-74, 1974.Grinberg, E. J. "Plane
Homogeneous Graphs of Degree Three without Hamiltonian Circuits." Latvian
Math. Yearbook, Izdat. Zinatne, Riga4, 51-58, 1968.Grünbaum,
B. "Polytopes, Graphs, and Complexes." Bull. Amer. Math. Soc.76,
1131-1201, 1970.Grünbaum, B. "Vertices Missed by Longest Paths
or Circuits." J. Combin. Th. A17, 31-38, 1974.Read,
R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, p. 274, 1998.Sachs,
H. "Ein von Kozyrev und Grinberg angegebener nicht-Hamiltonischer kubischer
planarer Graph." In Beiträge zur Graphentheorie. Leipzig, Germany:
Teubner, pp. 127-130, 1968.Thomassen, C. "Planar Cubic Hypohamiltonian
and Hypotraceable Graphs." J. Comb. Th. B30, 36-44, 1981.Zamfirescu,
T. "On Longest Paths and Circuits in Graphs." Math. Scand.38,
211-239, 1976.
