Proving that a graph of a certain size is Hamiltonian 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.
 A: A graph on $n$ vertices can have at most $m=\frac{n(n-1)}{2}$ edges, $(K_n)$. The graph given in the problem statement, $G_n=(V,E)$, with $|V|=n$ and $|E|=m$  has $m\geq \frac {(n-1)(n-2)+4}{2}$ edges. Because $\frac{n(n-1)}{2}-\frac {(n-1)(n-2)+4}{2}=n-3$,  any $G_n$ can be created from $K_n$ by deleting exactly $n-3$ edges from $K_n$. 
A graph is hamiltonian if its closure, cl$(G)$, is hamiltonian. Consider the effects of subtracting an edge from $K_n$. Each subtracted edge reduces the degree of two vertices by one. 
You can proceed by induction on $\delta (G)$.
If all the subtracted edges are adjacent to a single vertex then that vertex will have degree $(n-1)-(n-3)=2$ thus $\delta(G_n)=2$ . Each other vertex in $G_n$, with $\delta(G_n)=2$ will have degree $(n-1)-1$. $n-2+2=n$ so the graph will close to $K_n$ and $G_n$ is hamiltonian. 
If $\delta (G)=3$ the next smallest degree vertex in $G_n$ can have degree $(n-1)-1-1=(n-3)$. $n-3+3=n$ so the graph will close to $K_n$ and $G_n$ is hamiltonian. 
If $\delta (G)=k+1$  the next smallest degree vertex in $G_n$ can have degree $(n-1)-k$.  $n-1-k+(k+1)=n$ so the graph will close to $K_n$ and $G_n$ is hamiltonian. 
A: Proof by induction on $n$. 
Let $G$ be a graph of order $n$ and size $m$ (given). Denote the maximum degree of a vertex of G by $\Delta$ and the average degree by $\delta$. Then
$$\delta = \frac{2m}{n} \geq \frac{(n-1)(n-2)+4}{n} \geq n-3+\frac{6}{n}$$
$\Delta \geq \delta$ and $\Delta\in \mathbb{Z}$, so $\Delta \geq n-2$. Let $v$ be a maximum degree vertex of G. 
$d(v)$ is $n-1$ or $n-2$.
Case 1: $d(v)=n-2$ 
$$e(G-v)= m-d(v)\geq \frac{(n-2)(n-3)}{2}+2$$
So, by induction hypothesis, $G-v$ contains a Hamiltonian cycle. Two adjacent vertices in this cycle are neighbors of $v$, so add v to the cycle and we are done.
Case 2: $d(v)=n-1$
Now the above doesn't quite hold, since $G-v$ contains 1 fewer edge than required. No problem! Let $H$ be $G-v$ with an arbitrary edge added (call this $jk$. By induction hypothesis, $H$ is Hamiltonian. If this cycle doesn't contain the added edge we are done, as in Case 1. Otherwise, deleting $jk$ gives a Hamiltonian path in $G-v$ from $j$ to $k$. $j\sim v$ and $k\sim v$, since $d(v)=n-1$, so we have a Hamiltonian cycle, as required.
Base case: easy.
Edit: A general tip 
I find it useful in problems like this to see how the numbers arise. Consider briefly why any fewer edges are insufficient.
A: You were on the right path. Possibly, you can do it way easier than I just did. However, this was how it came to mind for me. Note that I answered the question 'for higher $n$'. Perhaps it also works for $n \geq 3$, but I did not verify that. I'm sure that with more careful arguments (or simply bruteforce for $n=3$ and $n=4$) it should work.
Given a graph $G=(V,E)$ on $n$ vertices and $m$ edges, with $m = (n-1)(n-2)/2+1$. Suppose there is one pair of non-adjacent vertices $a$ and $b$ such that $d(a)+d(b) \leq n-1$ and that all other  pairs are either adjacent or the sum of their degrees is at least $n$.
Find a set of pairs of distinct vertices $(u_1,v_1), ... ,(a_k,v_k)$ such that $(u_i,v_i)$ are non-adjacent and all pairs (including $(a,b)$) are pairwise disjoint e.g. each vertex is in at most one pair.
Then, the set of vertices $C$ in the graph that are in no pair, $C := V \setminus ( \cup_{1 \leq i \leq k} u_i \cup_{1 \leq i \leq k} v_i \cup \{a,b\} )$ induces a clique in $G$. 
Let $H$ be a hamiltonian cycle in $G[V \setminus C]$. Let $w$ and $x$ be two adjacent vertices in $H$. Then, if there are two distinct vertices $y$ and $z$ in $C$ such that $wy \in E$ and $xz \in E$, there is an hamiltonian cycle for $G$. Therefore, if $w$ has one edge to $C$ and $x$ at least one, we are done. For a contradiction, assume that for all adjacent pair of vertices $w$ and $x$ in $H$, that either $x$ or $w$ has degree $0$ towards $C$. Then the total degree of this graph is at most*:


*

*Edges in $G[H]$ is at most $(n-|C|)(n-|C|-1)/2$  

*Edges in $G[C]$ is $|C|(|C|-1)/2$

*Edges between $H$ and $C$ is at most $(|H|/2) \cdot |C| = ((n-|C|)/2) \cdot |C|$


However, we know that we have $m = (n-1)(n-2)/2+1 = (n-|C|+|C|-1)(n-|C|+|C|-2)/2 +1$ 
$ = (n-|C|)^2 + 2(n-|C|)|C|-3(n-|C|)-3|C|+|C|^2+2$ edges.
Comparing the quantities we find out that this is a contradiction. Therefore, it is sufficient to find a hamiltonian cycle in $G[V \setminus C]$ and we will focus on that from this point.
*The other case is both have degree $1$ towards $C$, but the total number of edges is lower, so it's the easier case.
Writing out the idea that you also wrote in your question:
Each vertex, apart from $a$ and $b$ has degree at most $n-2$, so therefore we have at most $((n-2)(n-2)+n-1) /2)$ edges in the graph.


*

*$(n-2)(n-2)+n-1 \geq 2m = (n-2)(n-1) + 4 $

*$n^2-4n+4+n-1 \geq 2m = n^2-3n+2 + 4 $

*$n^2-3n+3 \geq 2m = n^2-3n+6 $


Which is a contradiction, therefore for any two non-adjacent vertices the sum of their degrees is at least $n$.
