At the moment I'm trying to prove the statement:
$K_n$ is an edge disjoint union of Hamiltonian cycles when $n$ is odd.
($K_n$ is the complete graph with $n$ vertices)
So far, I think I've come up with a proof. We know the total number of edges in $K_n$ is $n(n-1)/2$ (or $n \choose 2$) and we can split our graph into individual Hamiltonian cycles of degree 2.
We also know that for n vertices all having degree 2, there must consequently be $n$ edges. Thus we write $n(n-1)/2 = n + n + … n$ (here I'm just splitting $K_n$'s edges into some number of distinct Hamiltonian paths) and the deduction that $n$ must be odd follows easily.
However, the assumption I made – that we can always split $K_n$ into Hamiltonian paths of degree 2 if $K_n$ can be written as a disjoint union described above – I'm having trouble proving. I've only relied on trying different values for $n$ trials and it hasn't faltered yet. So, I'm asking:
If it is true, how do you prove that if $K_n$ can be split into distinct Hamiltonian cycles, it can be split in such a way that each Hamiltonian cycle is of degree 2?
Best Answer
What you are looking for is a Hamilton cycle decomposition of the complete graph $K_n$, for odd $n$.
An example of how this can be done (among many other results in the area) is given in: D. Bryant, Cycle decompositions of complete graphs, in Surveys in Combinatorics, vol. 346, Cambridge University Press, 2007, pp. 67–97.
Here is the starter cycle for a Hamilton cycle decomposition of $K_{13}$, given in the paper:
If you rotate the starter, you obtain the other Hamilton cycles in the decomposition.
The method of using a "starter" cycle under the action of a cyclic automorphism is typical in graph decomposition problems.