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, Bernhart and Kainen 1979, de Wet et al. 2018), illustrated above, is one of these, as is the Herschel graph.
The Goldner-Harary graph is implemented in the Wolfram Language as GraphData["GoldnerHararyGraph"].
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, as well as being a 3-tree.
The Goldner-Harary graph is shown above in a number of straight-line embeddings.
The Goldner-Harary graph has book thickness 3, thus providing an example of a planar graph with
book thickness 
.
The Goldner-Harary graph is the skeleton of the augmented triangular dipyramid, a construction described by Grünbaum (2003, p. 357), though without identification of the particular resulting graph. It is also the dual graph of the skeleton of the truncated triangular prism. The canonical polyhedron of this solid is termed the Goldner-Harary polyhedron in this work.
