Let $G$ be a simple graph with $\delta \geq n / 2$, where $n \geq 3 .$ Then $G$ has a Hamilton cycle. Theorem. Let $G$ be a simple graph with $\delta \geq n / 2$, where $n \geq 3 .$ Then $G$ has a Hamilton cycle.
My attempt:
Proof. By induction on $n$. The Theorem is true for $n=3$, because $G=K_{3}$ in this case. Suppose that it holds for $n=k$, where $k \geq 3$. Let $G^{\prime}$ be a simple graph on $k$ vertices in which $\delta \geq k / 2$, and let $C^{\prime}$ be a Hamilton cycle of $G^{\prime}$. Form a graph $G$ on $k+1$ vertices in which $\delta \geq(k+1) / 2$ by adding a new vertex $v$ and joining $v$ to at least $(k+1) / 2$ vertices of $G^{\prime} .$ Note that $v$ must be adjacent to two consecutive vertices, $u$ and $w$, of $C^{\prime} .$ Replacing the edge $u w$ of $C^{\prime}$ by the path $u v w$, we obtain a Hamilton cycle $C$ of $G$. Thus the Theorem is true for $n=k+1$. By the Principle of Mathematical Induction, it is true for all $n \geq 3$.
Is my proof correct? Does the theorem fail for any graphs?
 A: This is a classic mistake known as the "induction trap".
Not all graphs on $k+1$ vertices with minimum degree $\frac{k+1}{2}$ are obtained by adding a new vertex to a $k$-vertex graph with minimum degree $\frac k2$. So when your induction step assumes that the theorem holds for $G'$, and proves it for a graph $G$ obtained from $G'$ in this way, the proof will not apply to every possible $G$.
The proof structure that avoids the "induction trap" is to start with an arbitrary $(k+1)$-vertex graph $G$ with minimum degree $\frac{k+1}{2}$, somehow obtain from it a $k$-vertex graph $G'$ with minimum degree $\frac k2$, apply the inductive hypothesis to $G'$, and use it to prove the result for $G$.
Unfortunately, there is not a good way to do this. The problem is simply not, to the best of my knowledge, amenable to induction on the number of vertices.

I think that most people that have not seen similar results before will not be able to prove this theorem from scratch. But this is a famous result known as Dirac's theorem, and there are many proofs to be found in textbooks and online.
