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

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.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

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