Graph Theory. Decomposition of K_{2n+1} into hamiltonian cycles.

[caffeinemachine]

Theorem: Prove that there exist $n$ edge disjoint Hamiltonian cycles in the complete graph $K_{2n+1}$.
----------------------------------------------------------------------------------
I have found two constructive proofs of this over the internet. But I would like to prove it non-constructively.

This question can be easily framed in terms of permutations. One has to prove that in $S_{2n+1}$ there exist $n$ permutations $\sigma_1, \ldots, \sigma_n$ such that the cycle decomposition of each contains exactly one cycles and that if two elements of $\{ 1,2,\ldots , 2n+1 \}$ appear consecutively in the cycle decomposition of $\sigma_i$ then then they don't appear consecutively in the cycle decomposition of $\sigma_j \, \forall j \neq i$.

For example, consider $S_5$. Then $\sigma_1 = (1 \, 2 \, 3 \, 4 \, 5)$ and $\sigma_2 = (1 \, 3 \, 5 \, 2 \, 4)$ fill the bill.

The theorem is also equivalent to the following:
$K_{2n}$ can be decomposed into $n$ Hamiltonian paths.

 

[caffeinemachine]

Theorem: Prove that there exist $n$ edge disjoint Hamiltonian cycles in the complete graph $K_{2n+1}$.
----------------------------------------------------------------------------------
I have found two constructive proofs of this over the internet. But I would like to prove it non-constructively.

This question can be easily framed in terms of permutations. One has to prove that in $S_{2n+1}$ there exist $n$ permutations $\sigma_1, \ldots, \sigma_n$ such that the cycle decomposition of each contains exactly one cycles and that if two elements of $\{ 1,2,\ldots , 2n+1 \}$ appear consecutively in the cycle decomposition of $\sigma_i$ then then they don't appear consecutively in the cycle decomposition of $\sigma_j \, \forall j \neq i$.

For example, consider $S_5$. Then $\sigma_1 = (1 \, 2 \, 3 \, 4 \, 5)$ and $\sigma_2 = (1 \, 3 \, 5 \, 2 \, 4)$ fill the bill.

The theorem is also equivalent to the following:
$K_{2n}$ can be decomposed into $n$ Hamiltonian paths.

If $2n+1$ is a prime then there is a trivial construction.
The cycles $(1, \, 1+i, \, 1+2i, \, \ldots , \, 1+2ni), i \in \{1,2, \ldots , n \}$ do the job.

 

[Sudharaka]

Theorem: Prove that there exist $n$ edge disjoint Hamiltonian cycles in the complete graph $K_{2n+1}$.
----------------------------------------------------------------------------------
I have found two constructive proofs of this over the internet. But I would like to prove it non-constructively.

This question can be easily framed in terms of permutations. One has to prove that in $S_{2n+1}$ there exist $n$ permutations $\sigma_1, \ldots, \sigma_n$ such that the cycle decomposition of each contains exactly one cycles and that if two elements of $\{ 1,2,\ldots , 2n+1 \}$ appear consecutively in the cycle decomposition of $\sigma_i$ then then they don't appear consecutively in the cycle decomposition of $\sigma_j \, \forall j \neq i$.

For example, consider $S_5$. Then $\sigma_1 = (1 \, 2 \, 3 \, 4 \, 5)$ and $\sigma_2 = (1 \, 3 \, 5 \, 2 \, 4)$ fill the bill.

The theorem is also equivalent to the following:
$K_{2n}$ can be decomposed into $n$ Hamiltonian paths.

Hi caffainmachine, :)

I don't know the answer to your question, however I found that the exact same question is asked in "mathoverflow".

Link: Hamilton Paths in $K_{2n}$ - MathOverflow

Note that in the answer given it says,

"More generally, a symmetric sequencing in a group with a single involution is sufficient to construct the decomposition."

I don't have a clear understanding about what this statement means, however just thought of quoting it here 'cause I felt that it might lead to a Group theoretical proof to your question.

Kind Regards,
Sudharaka.