Let G be a graph of order $n$ with $e(G)>{n\choose2}-(n-2)$. Prove that $G$ is Hamiltonian.
On my way use induction, the basis step is clear.
But induction step assume that $G_1=G+x$ for all $x\notin V(G)$ with $e(G_1)>{n+1\choose2}-(n+1-2)$,
For induction hypothesis when should i use it?
Remark $e(G)=|E(G)|$.
Let $G$ be a graph of order $n\gt3$ and size $e(G)\gt\binom n2-n+2=\binom{n-1}2+1$.
By the inductive hypothesis, the proposition holds for all graphs of order less than $n$.
Claim. $G$ contains a vertex $x$ of degree $\deg(x)\gt\frac{n-1}2$.
Proof. Otherwise we would have $$2e(G)=\sum_{x\in V(G)}\deg(x)\le\frac{n(n-1)}2=\binom n2$$ so that $e(G)\le\frac12\binom n2$, but this contradicts our hypothesis that $e(G)\gt\binom n2-n+2\gt\frac12\binom n2$.
Choose a vertex $v\in V(G)$ of degree $d(x)=d\gt\frac{n-1}2$. Then $G-x$ is a graph of order $n-1$, and $$e(G-x)=e(G)-d\gt\binom{n-1}2+1-d.$$
Case 1. $d\le n-2$.
Then $e(G-x)\gt\binom{n-1}2+1-(n-2)=\binom{n-1}2-(n-1)+2$. Therefore, by the inductive hypothesis, the graph $G-x$ has a Hamiltonion circuit $C$. Since $\deg(x)\gt\frac{n-1}2$, the vertex $x$ is joined to two consecutive vertices of $C$, so there is also a Hamiltonian cycle in $G$.
Case 2. $d=n-1$, i.e., $x$ is joined to all other vertices of $G$.
If $G-x$ is a complete graph, then $G$ is a complete graph and there's nothing to prove. Otherwise, let $u,v$ be two nonadjacent vertices of $G-x$, and let $H=G-x+uv$, a graph of order $n-1$ and size $e(H)=e(G-x)+1\gt\binom{n-1}2+2-d=\binom{n-1}2-(n-1)+2$. By the inductiove hypothesis, the graph $H$ has a Hamiltonian circuit $C$. If $uv\in E(C)$ then $C-uv+ux+xv$ is a Hamiltonian circuit of $G$. If $uv\notin E(C)$, choose any edge $yz\in E(C)$; then $C-yz+yx+xz$ is a Hamiltonian circuit of $G$.
Remark. This is best possible; for each $n\ge2$ there is an obvious example of a
non-Hamiltonian graph with $n$ vertices and $\binom{n-1}2+1$ edges.