# 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

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). 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.