Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

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|improve this question
add comment

1 Answer 1

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|improve this answer
    
Thank you Matt. –  Leandro Apr 6 '11 at 23:51
add comment

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.