Prove this graph must have a Hamilton circuit Assume G is a simple graph with $n>3$ vertices. Prove that if the number of its edges is more than $\binom{n-1}{2} + 2$, then it has a Hamilton circuit.
Any hints?
 A: Suppose that $\delta$ is the minimum degree of $G$.
If $\delta =n-1$ or $\delta=2$, then there is nothing to prove. So suppose that $\delta ‎\leq‎ n-2$. Let $v$ be the vertex of degree $\delta$. In $G ‎\setminus‎ v$, the number of edges is $m'‎\geq‎ \genfrac{(}{)}{0pt}{}{n-1}{2}-(\delta-2)‎$. We claim that  $\genfrac{(}{)}{0pt}{}{n-1}{2}-(\delta-2)‎ \geq \genfrac{(}{)}{0pt}{}{n-2}{2}+2$. 
Because:
$\genfrac{(}{)}{0pt}{}{n-1}{2}-(\delta-2)‎ \geq \genfrac{(}{)}{0pt}{}{n-2}{2}+2 \Leftrightarrow‎ n-2 \geq \delta$. 
So this is correct.
Now, by induction on $n$, $G\setminus v$ has a hamiltonian cycle $C$.
Suppose that the neighbors of ‎$‎v‎$‎‏ are ‎$‎v_1, ..., v_\delta‎$‎‏ ‎and‎‎‎‎ ‎$‎v_i‎$‎‏ is adjacent ‎$‎v_j‎$‎‏ by an edge ‎$‎e‎$‎‏.‎
If ‎$‎e‎$‎‏ is on the cycle ‎$‎C‎$‎‏, then we have a hamiltonian cycle in ‎$‎G‎$‎‏.‎
‎
So suppose that non of edges between the neighbors of ‎$‎v‎$‎‏ is on cycle ‎$‎C‎$‎‏. ‎
‎
Now, assume that the vertices before and after the vertex ‎$‎v_i‎$‎‏ (clockwise), (in cycle ‎$‎C‎$‎‏) is ‎$‎v_{i_1}‎$‎‏ and ‎$‎v_{i_2}‎$‎‏ and the similar name for ‎$‎v_j‎$‎‏. If the vertices ‎$‎v_{i_1}‎$‎‏ and ‎$‎v_{j_1}‎$‎‏ or the vertices ‎$‎v_{i_2}‎$ ‎and ‎‎$‎v_{j_2}‎$‎‏ ‎are ‎adjacent‎‏, then we can form a hamiltonian cycle. Therefore suppose that for any two pair of vertices of neighbors ‎$‎v‎$‎‏, the graph ‎$‎G\setminus v‎$‎‏ does not  have these two kind of edges. So we have:‎
‎
‎$‎m'‎\leq‎ \genfrac{(}{)}{0pt}{}{n-1}{2} -2\genfrac{(}{)}{0pt}{}{\delta}{2}‎$‎‏‎‎.‎
‎
So we have :‎
‎
$‎2\genfrac{(}{)}{0pt}{}{\delta}{2} \leq \delta -2‎$‎‏‎.
‎
And it is a contradiction.
A: First of all, notice that the number of the non-edges in the graph is at most $n-3$. 
In the case of the complete graph the result is clear. Therefore suppose that the considered graph is not complete. Thus there are some pairs of vertices $u$ and $v$ such that $uv\notin E$. If for all such pairs $\deg(u)+\deg(v)\geq n$, then Ore's theorem solves the problem. Otherwise, there exists a pair of vertices, say $x$ and $y$ such that $xy\notin E$ and $\deg(x)+\deg(y)\leq n-1$.
Now, let us count the number of missing edges that are incident to $x$ or $y$. 
Clearly $xy$ is one such edge. From the remaining $2\cdot(n-2)$ possibilities at most $n-1$ is an edge, and at least $n-3$ is a non-edge in the graph. 
Thus, the number of missing edges is at least $1+(n-3)>n-3$, a contradiction. Thus, there are no such pairs $x,y$ for which $\deg(x)+\deg(y)<n$, therefore the graph does contain a Hamilton cycle. 
