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 ?