2
$\begingroup$

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?

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

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$.

Longest path 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.)

Showing the neighbours u' and v'

Thus we have a cycle formed as illustrated below:

cycle

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:

A path longer than P

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.