A maximally nonhamiltonian graph is a nonhamiltonian graph 
for which 
is Hamiltonian for each graph
edge 
in its graph complement 
, i.e., every two nonadjacent vertices
are endpoints of a Hamiltonian path.
A graph edge added between two connected components of a disconnected graph is a graph bridge. Since a Hamiltonian cycle cannot use a graph bridge, every maximally nonhamiltonian graph is connected.
Under MathWorld's convention, the singleton graph 
is Hamiltonian and therefore is excluded. The
path graph 
is nonhamiltonian
and has an empty graph as its graph
complement, so it is maximally nonhamiltonian by the vacuous edge-addition condition.
The numbers of maximally nonhamiltonian graphs on 
, 2, ... vertices are 0,
1, 1, 1, 3, 3, 7, 9, 18, 31, ... (OEIS A185306),
the first few of which are illustrated above. Larger examples include the Coxeter
graph, flower snarks 
for odd 
, Petersen graph, and
Tietze graph (Clark and Entringer 1983).
A maximally nonhamiltonian graph 
is a platypus graph iff 
(Zamfirescu 2017, Goedgebeur et al. 2020), where 
is the maximum
vertex degree and 
is the vertex count.
