A graph is called maximally non-hamiltonian, if it does not contain a hamilton-cycle, but no edge can be added without creating a hamilton-cycle. In other words, every pair of non-adjacent vertices $(u/v)$ can be connected with a hamiltonian path.
- How can the maximally non-hamiltonian graphs be classified with known graph properties ?
Using the edge count. If there is a non-Hamiltonian graph $G$ on $n$ vertices, the maximal number of edges that $G$ can contain is ${n-1\choose 2} +1 = {n\choose 2} - (n-2).$