A polyhedral nonhamiltonian graph is a graph that is simultaneously polyhedral
and nonhamiltonian.

The smallest possible number of vertices a nonhamiltonian polyhedral graph can have is 11, and there exist 74 such graphs, as summarized in the table below.

Sloane, N. J. A. Sequence A007033/M5351 in "The On-Line Encyclopedia of Integer Sequences."Tait, P. G.
"Remarks on the Colouring of Maps." Proc. Royal Soc. Edinburgh10,
729, 1880.Tutte, W. T. "On Hamiltonian Circuits." J.
London Math. Soc.21, 98-101, 1946.Tutte, W. T. "Non-Hamiltonian
Planar Maps." In Graph
Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 295-301,
1972.