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).

Bollobás, B. Extremal Graph Theory. New York: Academic Press, p. 167, 1978.Bondy,
J. A. "Variations on the Hamiltonian Theme." Canad. Math. Bull.15,
57-62, 1972.Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian
Graphs." Periodica Math. Hungarica14, 57-68, 1983.Sloane,
N. J. A. Sequence A185306 in "The
On-Line Encyclopedia of Integer Sequences."