The smallest possible number of vertices a polyhedral nonhamiltonian graph can have is 11, and there exist 74 such graphs. The Goldner-Harary
graph (Goldner and Harary 1975a, de Wet et al. 2018), illustrated above, is
one of these, as is the Herschel graph.
The Goldner-Harary graph has 11 vertices and 27 edges. It is exceptional for being the unique smallest nonhamiltonian simplicial graph, meaning it is the only 11-vertex
nonhamiltonian polyhedral that contains of only
triangular faces. It is also the unique 11-vertex nonhamiltonian polyhedral graph
having the maximum possible 27 edges. It is also a 3-tree.
The Goldner-Harary graph is shown above in a number of straight-line embeddings.
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.Read,
R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, p. 285, 1998.
