Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Nothing. It is obvious, for the reason you state. –  Andres 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. –  Andres 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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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