The Goldner-Harary graph is an 11-vertex polyhedral nonhamiltonian graph (Goldner and Harary 1975a, Bernhart and Kainen 1979, de
Wet et al. 2018), illustrated above. Eleven is the smallest possible vertex
count of such a graph, and there exist 74 such graphs,
including the Herschel graph.
The Goldner-Harary graph has 11 vertices and 27 edges. It is exceptional for being the unique smallest
nonhamiltonian graph with only triangular
faces, meaning it is the only 11-vertex nonhamiltonian
polyhedral graph with this property. It is also
the unique 11-vertex nonhamiltonian polyhedral graph
having the maximum possible 27 edges, as well as being
a k-tree with .
The Goldner-Harary graph is shown above in a number of straight-line graph drawings.
Bernhart, F. and Kainen, P. "The Book Thickness of a Graph." J. Combin. Th. Ser. B27, 320-331, 1979.de
Wet, J. P.; Frick, M.; and van Aardt, S. A. "Hamiltonicity of Locally
Hamiltonian and Locally Traceable Graphs." Disc. Appl. Math.236,
137-152, 2018.Dillencourt, M. B. "Polyhedra of Small Orders
and Their Hamiltonian Properties." Tech. Rep. 92-91, Info. and Comput. Sci.
Dept. Irvine, CA: Univ. Calif. Irvine, 1992.Dillencourt, M. B.
"Polyhedra of Small Orders and Their Hamiltonian Properties." J. Combin.
Th.66, 87-122, 1996.Goldner, A. and Harary, F. "Note
on a Smallest Nonhamiltonian Maximal Planar Graph." Bull. Malaysian Math.
Soc.6, No. 1, 41-42, 1975a.Goldner, A. and Harary,
F. "Note on a Smallest Nonhamiltonian Maximal Planar Graph." Bull. Malaysian
Math. Soc.6, No. 2, 33, 1975b.Goldner, A. and Harary,
F. "Note on a Smallest Nonhamiltonian Maximal Planar Graph." Bull. Malaysian
Math. Soc.8, 104-106, 1977.Grünbaum, B. Convex
Polytopes, 2nd ed. New York: Springer-Verlag, p. 357, 2003.House
of Graphs. "Goldner Harary Graph." https://houseofgraphs.org/graphs/1110.Read,
R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, p. 285, 1998.
.
.
