A quintic nonhamiltonian graph is a quintic graph that is nonhamiltonian. A number of such
graphs are illustrated above.
Owens (1980) showed that there exists a nonhamiltonian quintic polyhedral graph on 76 vertices, and van Cleemput and Zamfirescu (2018) demonstrated that
there exists such a graph for every even . van Cleemput and Zamfirescu (2018) also demonstrated
that the smallest possible such graph must have .
van Cleemput and Zamfirescu (2018) showed that there exists a nonhamiltonian quintic polyhedral graph on vertices for every even , with no better lower bound presently known. Their
proof relied on a construction involving the rhombic
dodecahedral graph.
Harant, J.; Owens, P. J.; Tkáč, M; and Walther, H. "5-Regular 3-Polytopal Graphs with Edges of Only Two Types and Shortness
Exponents Less Than One." Disc. Math.150, 143-153, 1996.Owens,
P. J. "On Regular Graphs and Hamiltonian Circuits, Including Answers to
Some Questions of Joseph Zaks." J. Combin. Theory, Ser. B28,
262-277, 1980.van Cleemput, N. and Zamfirescu, C. T. "Regular
Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput.338 192-206,
2018.Walther, H. "A Non-Hamiltonian Five-Regular Multitriangular
Polyhedral Graph." Disc. Math.150, 387-392, 1996.
. van Cleemput and Zamfirescu (2018) also demonstrated
that the smallest possible such graph must have 
.
vertices for every even 
, with no better lower bound presently known. Their
proof relied on a construction involving the rhombic
dodecahedral graph.
