- Thread starter
- #1

- Mar 10, 2012

- 835

----------------------------------------------------------------------------------

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.