Let $G$ be a graph on $n$ vertices with size at least ${n\choose 2} - (n-2)$. Show that $G$ is Hamiltonian. What is the unique Extremal graph?
The first part I did. I even know the Extremal graph should be $K_{n-1}$ together with a vertex of degree 1. The way I have been trying to prove this is by considering $K_n$ and removing edges, specifically, $n-2$ edges. My goal is to show that the only way to avoid a Hamiltonian graph is to do this by removing all the edges from one vertex.
A graph is Hamiltonian if it's minimal degree is $n/2$, by Dirac's Theorem, so I need to remove $k$ edges from, say a vertex $x$ so that $d(x) = \delta(G) < n/2$. In $K_n$, the degree of $x$ is $n-1$, so I need to remove $\lceil(n-2)/2\rceil$ edges incident with $x$. Then, there are at most $(n-2)/2$ edges left to remove from $n-1$ vertices, so each of these have degree at least $n/2$.
Now I have a graph with a vertex of degree $d(x)<n/2$ and a subgraph with $n-1$ vertices and a Hamilton cycle. I just need to show I can extend this to a Hamilton cycle containing $x$.
My thought was to follow a proof of Dirac's Theorem and construct a maximal path containing $x$. This must contain all the neighbors of $x$, or else it is not maximal. Where I am struggling is how do I guarantee that $x$ is not an end vertex of this path and actually find a cycle?
We prove the contrapositive. If $G$ is complete, then we are done. Suppose not. Then there are nonadjacent vertices $x$ and $y$. Set $G'=G-x-y$. Note that $${n\choose 2} - {n-1\choose 2} = \frac{(n-1)[n-(n-2)]}{2} = n-1$$ so that $${n\choose 2} - (n-2)= {n-1\choose 2}+1.$$ Since we assume that $e(G) > {n\choose 2} - (n-2)= {n-1\choose 2}+1,$ it follows that $${n-1\choose 2}+1- d(x)-d(y) < e(G') \leq {n-2\choose 2},$$ where the upper bound comes from the complete graph on $n-2$ vertices. Algebra reveals that \begin{align*} {n-1\choose 2}-{n-2\choose 2}+1&= \frac{(n-2)[(n-1)-(n-3)]}{2} +1\\ &= n-1 < d(x) + d(y), \end{align*} and this is equivalent to $$d(x) +d(y) \geq n,$$ which is the condition for $G$ to be Hamiltonian.
To see the extremal graph is unique, suppose $G$ is extremal. Since there are ${n\choose 2}-(n-2)$ edges, and $G$ is not Hamiltonian, we must have that $\delta(G) <n/2$. If $d(x) = \delta(G)$, we know \begin{align*} d(x) &=n-1-k\\ &<n/2 \end{align*} Thus, \begin{align*} 2n-2-2k &<n\\ \frac{n-2}{2} &< k. \end{align*} However, there is at most one vertex of this degree. If not, then we subtracted $(n-2)/2$ edges from at least two vertices in $K_n$, which is impossible. Thus, considering $G'=G-x$, we see that $\delta(G') \geq n/2$, so $G'$ is Hamiltonian.
Suppose that $d(x) \geq 2$. Take a maximal path in $G$ containing $x$, say $P=x_0x_1\cdots x_m$, where $x_0,x_m\in G'$. Such a path must exist if $d(x) \geq 2$. Moreover, we see that all the neighbors of $x_0$ and $x_m$ must be in $P$. At least $n/2$ of the vertices of $P-x_0$ are adjacent to $x_0$ and at least $n/2$ in $P-x_m$ are adjacent to $x_m$. Since $d(x_0)+d(x_m) \geq n$ and the length of $P$ is at most $n$, we see that, for some $x_i$ with $0\leq i\leq m-1$, $x_ix_m$ and $x_0x_{i+1}$ are edges in $G$. The path $x_0x_{i+1}\cdots x_{m-1}x_mx_i\cdots x_1x_0$ is a Hamilton cycle in $G$, contradicting the fact that $G$ is extremal. Thus, no such path exists, contradicting the fact that $d(x) \geq 2$. Thus, $d(x) \leq 1$. Clearly $d(x) \neq 0$ and, therefore, we must have removed $n-2$ vertices from $x$ in $K_n$ to construct $G$. As every edge removed from $x$ in $K_n$ while constructing $G$ decreases the degree of one vertex by 1, and each vertex has only one edge joining it to $x$, the graph $G'$ is $K_{n-1}$.