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 ?


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.


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.