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

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?

• Nothing. It is obvious, for the reason you state. – Andrés E. Caicedo Aug 3 '13 at 1:45
• What is meant by "[s]how"? – Trancot Aug 3 '13 at 3:42
• Good question. It means "prove", but what precisely is a valid proof is much more subjective and difficult to specify. – Andrés E. Caicedo Aug 3 '13 at 3:46
• I don't know. I think the author of the book went on vacation, and had an editor friend take over that chapter... – Trancot Aug 3 '13 at 4:02

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.