Grinberg Graphs


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.

See also

Barnette-Bosák-Lederberg Graph, Faulkner-Younger Graphs, Nonhamiltonian Graph, Tait's Hamiltonian Graph Conjecture, Tutte's Graph

Explore with Wolfram|Alpha


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, Riga 4, 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. A 17, 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. B 30, 36-44, 1981.Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

Referenced on Wolfram|Alpha

Grinberg Graphs

Cite this as:

Weisstein, Eric W. "Grinberg Graphs." From MathWorld--A Wolfram Web Resource.

Subject classifications