Prove this graph must have a Hamilton circuit

Question

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?

Answer 1

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.

Answer 2

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.