0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bob Krueger Dec 28 '17 at 19:20
0
$\begingroup$

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

$\endgroup$

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.