A Hamiltonian graph is a graph which has a Hamiltonian cycle.
A Hamiltonian cycle is a cycle which crosses all of the vertices of a graph. According to Ore's theorem , if $p \ge 3$ we have this :
For each two non-adjacent vertices $u,v$ , if $\deg(u)+\deg(v) \ge p$, then the graph is Hamiltonian.
Now suppose that we have a graph with $p$ vertices and $2+(p-1)(p-2)/2$ edges. How can we prove that this graph is Hamiltonian ?
Best Answer
Suppose there were two non-adjacent vertices with $\deg(u) + \deg(v) < p$.
Then delete those two vertices and all edges connected to them. (the number of edges deleted is at most $p-1$)
We are left with a graph with $p-2$ vertices and at least $2 + (p-1)(p-4)/2$ edges, which is one more than $(p-2)(p-3)/2$, the latter being the most edges that a graph with $p-2$ vertices can have. Thus, we get a contradiction.