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

AI Thread Summary
The discussion centers on proving the existence of n edge-disjoint Hamiltonian cycles in the complete graph K_{2n+1} using a non-constructive approach. It is suggested that this can be framed in terms of permutations within S_{2n+1}, requiring n permutations where consecutive elements in one permutation do not appear consecutively in others. An example from S_5 illustrates this concept with specific permutations. Additionally, the theorem is linked to the decomposition of K_{2n} into n Hamiltonian paths, and a reference to a related question on MathOverflow suggests a potential group-theoretical proof. The conversation highlights the complexity and interconnectedness of graph theory concepts.
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
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.
 
Physics news on Phys.org
caffeinemachine said:
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.
 
caffeinemachine said:
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.
 

Similar threads

Replies
1
Views
2K
Replies
2
Views
2K
Replies
3
Views
2K
Replies
28
Views
3K
Replies
1
Views
2K
3
Replies
100
Views
11K
4
Replies
175
Views
25K
Back
Top