Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle. I'm asked the following quesiton:


Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle.


This seems obvious since $K_n$ contains a subgraph which is a cycle graph hitting all $n$ vertices. What am I missing here?
 A: In fact, a stronger result holds:

Dirac's Theorem:  If every vertex of an $n$-vertex simple graph $G$ has degree $\geq n/2$, then $G$ is Hamiltonian.

Here's a proof.
Since every vertex in $G$ has degree $\geq n/2$, we find $K_n$ is connected (and, in fact, every pair of non-adjacent vertices must have a common neighbour).
Let $P$ denote the longest path in $K_n$, and let $u$ and $v$ be the endpoints of $P$.

We observe that all of the neighbours of both $u$ and $v$ lie in $P$ (otherwise, we there would be a longer path than $P$).
Since $u$ and $v$ both have degree $\geq n/2$ (and there are at most $n$ vertices in $P$), the vertices $u$ and $v$ have neighbours $u'$ and $v'$, respectively, such that $v'$ comes directly before $u'$ when walking from $u$ to $v$ in $P$.  (This can be argued more formally via the pigeonhole principle.)

Thus we have a cycle formed as illustrated below:

Since $G$ is connected, there is a path from any vertex to this cycle.  However, if the cycle has a neighbour outside of the cycle, we can construct a path longer than $P$, giving a contradiction.  An example is illustrated below:

We conclude that every vertex occurs in the cycle, and thus the cycle is a Hamilton cycle.
