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?
Best Answer
In fact, a stronger result holds:
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.