Maximally Nonhamiltonian Graph

A maximally nonhamiltonian graph is a nonhamiltonian graph G for which G+e is Hamiltonian for each edge e in the graph complement of G^_, 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 P_2 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 n1=, 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 J_k for odd k>=3, Petersen graph, and Tietze's graph (Clark and Entringer 1983).

See also

Almost Hamiltonian Graph, Hamilton-Connected Graph, Nonhamiltonian Graph

Explore with Wolfram|Alpha


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. Hungarica 14, 57-68, 1983.Sloane, N. J. A. Sequence A185306 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Maximally Nonhamiltonian Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications