Hamiltonian Cycle Problem 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?


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.

For odd $n$, let $n=2r+1$, take $\mathbb{Z}_{2r} \cup \{\infty\}$ as
  the vertex set of $K_n$ and let $D$ be the orbit of the $n$−cycle
\[(\infty, 0, 1, 2r − 1, 2, 2r − 2, 3, 2r − 3,\ldots , r − 1, r + 1,
  r)\]
under the permutation $\rho_{2r}$ [Here
  $\rho_{2r}=(0,1,\ldots,2r-1)$]. Then $D$ is a decomposition of $K_n$
  into $n$-cycles.

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.
