# $K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles

Show that (the edges) in the complete graph $K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles.

Further, show that (the edges) in the complete graph $K_n$ for all $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of paths, each of different length.

Hi everyone, I'm not sure how to show that $K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union of Hamiltonian cycles or that $K_n$ for all $n$ $ϵ$ $Z_+$ is a disjoint union of paths.

Thanks for all the help

• As an additional hint, for problems like these where induction is suggestive, it may help to prove a stronger claim. For instance, for the first proposition you may try to prove that not just can $K_n$ be decomposed into Hamiltonian cycles, but that these Hamiltonian cycles are arranged in a particular way (that you figure out and specify). This additional information provided in a stronger claim can make the induction step much easier. – Bob Krueger Dec 28 '17 at 19:20

## 1 Answer

Both the question are solved.

Answer for the first question (Walecki Construction):

Let the vertices of $K_n$ be labeled $v_0,\, v_1, . . . , v_{2m},\, n=2m+1.$ Let $C = v_0 v_1 v_2 v_{2m} v_3 v_{2m−1}$v_4$v_{2m−2} · · · v_{m+3} v_m v_{m+2} v_{m+1} v_0$ and let $σ$ be the permutation $(v_0)(v_1v_2v_3 · · · v_{2m−1}v_{2m}).$ Then $C_0 = C, C_1 = σ(C), C_2 = σ^2(C), . . . , C_{m−1} = σ^{m−1}(C)$ is a Hamilton cycle decomposition of Kn.

Answer for the second question: The link which given below will help you. https://www.sciencedirect.com/science/article/pii/S009589560900063X