MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


I am teaching this semester graph theory for undergraduate students. Now, I am discussing with them about Hamilton Paths in finite graphs. Last time we meet, I presented the following theorem:

Theorem. For $n\geq 3$ the complete graph $K_n$ is decomposable into edge disjoint Hamilton cycles iff n is odd. For $n\geq 2$ the complete graph $K_n$ is decomposable into edge disjoint Hamiltonian paths iff $n$ is even.

During the class I noted that my argument to prove this theorem was not complete. I started proving that the second statement implies the first one, which is ok. But I had not a correct argument to show that there exist an edge disjoint decomposition of $K_n$ in $n/2$ Hamilton paths if $n$ is even.

Can we explicitly construct such decomposition or just present an existence argument ?

share|cite|improve this question
up vote 8 down vote accepted

We can explicitly construct such a decomposition.

Label the vertices of the graph with $\{0,1,...,n-1\}$, take the first path to be $0, n-1, 1, n-2, 2,... ,n/2$ and generate the other paths by addition modulo $n$ (the $n$ paths come in pairs in which one is the reverse of the other).

More generally, a symmetric sequencing in a group with a single involution is sufficient to construct the decomposition.

share|cite|improve this answer
Thank you Matt. – Leandro Apr 6 '11 at 23:51

Your Answer


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.