For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian.
I know that if I can show that the degree sum of any two non-adjacent vertices is $\geq n$, then I'd be done.
Likewise, if I could show that the above somehow implied that the degree of every vertex in the graph is $\geq n/2$, I'd also be done. However, I cannot see how to get to either one of those given the information I have. I have been trying the following: assuming that there exists two non-adjacent vertices $u$ and $v$ whose degree sum is $\leq (n-1)$, then $$2m = \sum d\text{(other vertices))} + d(u) + d(v) \leq \sum d(\text{other vertices)} + (n-1).$$ If I could show that this implied that $$2m < \left(n-1\right)(n-2) + 4,$$ I would have a contradiction, thereby proving that the graph is Hamiltonian. However, I have not been able to show this, so I am thinking it is the wrong approach.