Proof that if graph has $\frac{(n-1)(n-2)}{2} + 2$ edged then contains hamiltonian cycle
I think that it is good to use there induction:
Let check base of induction. For $ n= 3 $ I have
$$ |E| = \frac{2\cdot1}{2}+2 = 3 \text{ and }n \text{ vertices }$$
so this is just triangle and triangle contains hamiltonian cycle.
Assume that
$$ \text{if graph with |V| = n has }\frac{(n-1)(n-2)}{2} + 2 \text{ edges then contains hamiltonian cycle } $$
Proof that
$$ \text{if graph with |V| = n+1 has }\frac{n(n-1)}{2} + 2 \text{ edgesthen contains hamiltonian cycle } $$
In this step I checked how many edges I have added:
$$\frac{1}{2} (n-1) n-\frac{1}{2} (n-2) (n-1) = n-1 $$
Now I should show that if I add $n-1$ edges in any way to my first graph, it will have hamiltonian cycle, but there I have stucked
Best Answer
Let $G$ be a graph with $n$ vertices and at least $\frac{(n-1)(n-2)}2+2$ edges. Suppose we find a vertex $v$ with $\frac{n-1}2<\rho(v)<n-1$. Then by removing $v$, we obtain a graph on $n-1$ vertices and (due to the right inequality) at least $\frac{(n-2)(n-3)}2+2$ edges. We may assume by induction that this has a Hamiltonian cycle. By the left inequality, $v$ is neigbour to more than half the vertices, hence to two consecutive vertices in this cycle and we can insert $v$ between those, thus finding a Hamiltonian cycle for the original graph.
Therefore, we may assume that all vertices have either $\rho(v)=n-1$ or $\rho(v)\le \frac{n-1}2$. If there are $k$ vertices of degree $\le\frac{n-1}2$, we count at most $$\frac{(n-k)(n-1)+k\frac{n-1}2}2 =\frac{(n-1)(2n-k)}4$$ edges. Hence $$ \frac{(n-1)(2n-k)}4\ge \frac{(n-1)(n-2)}2+2,$$ or $$\tag1k\le 4-\frac 8{n-1}.$$ We conclude $k\le 3$. But if $v$ is one of these $k$ vertices, we also have $\frac{n-1}2\ge\rho(v)\ge n-k$, or $$\tag2 k\ge \frac{n+1}2.$$ Combined, $4-\frac 8{n-1}\ge \frac{n+1}2 $, or after rearranging $$ 0\ge {n^2}-8n+23=(n-4)^2+7,$$ which is absurd.