Proof that if graph has $\frac{(n-1)(n-2)}{2} + 2$ edged then contains hamiltonian cycle 
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
 A: 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.
