How many edge-disjoint Hamilton cycles are there in the complete graph $K_{n}$ for $n$ odd

1.5k Views Asked by At

I was originally working on a problem that asked to find all edge-disjoint Hamilton cycles of $K_{21}$.

My first idea was to make an arbitrary cycle:

$v_{21}-v_{20}-v_{19}-v_{18}-v_{17}-v_{16}-v_{15}-v_{14}-v_{13}-v_{12}-v_{11}-v_{10}-v_{9}-v_{8}-v_{7}-v_{6}-v_{5}-v_{4}-v_{3}-v_{2}-v_{1}$

There are $21$ edges, since we are looking at edge-disjoint, we can't use those edges anymore, thus there are $210-21=189$ edges left to make more Hamilton cycles. For every Hamilton cycle, I use up $21$ edges each time, thus at most $10=\frac{(21-1)}{2}$ cycles?

Is there a better method for the general case $n$ odd?

I tried with some simple cases like $|V|=5,7$

For $n$ even, this is covered here.

1

There are 1 best solutions below

4
On BEST ANSWER

That is correct. The result is mentioned in the question you link to. Each vertex of $K_n$ has $n-1$ edges incident on it. Each cycle uses up two of those, so if you can find $\frac {n-1}2$ disjoint Hamiltonian cycles you have used up all the edges. That is clearly an upper bound.

To prove that the upper bound can be achieved you need to find that many cycles that do not reuse an edge. If $n$ is prime you can just have one cycle where each vertex connect to the one before and the one after in your list, one cycle where they connect two before and two after $\left(\bmod n\right)$, one where they connect three before and three after, and so on. For composite $n$ you need to be a little more clever because when you try to add a number not coprime to $n$ you will come back to where you started before you have visited all the vertices. You can do this by starting that way and getting a number of loops, then connecting the loops.