A maximally nonhamiltonian graph is a nonhamiltonian graph for which is Hamiltonian for each edge in the graph complement of , i.e., every two nonadjacent vertices are endpoints of a Hamiltonian path.
Since an edge added between two disconnected components of a disconnected graphs is a bridge, and after crossing a bridge in one direction, a Hamiltonian cycle cannot "cross back" in the other, it can be seen that only connected nonhamiltonian graphs can be maximally nonhamiltonian.
The status of the path graph is debatable since it is nonhamiltonian but has empty graph complement, but by a strict interpretation that "all 0 of its complement's edges result in a Hamiltonian graph," it should be considered maximally nonhamiltonian.
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 the Coxeter graph, flower snarks for odd , Petersen graph, and Tietze's graph (Clark and Entringer 1983).