# Problem about Number of Distinct Hamiltonian Cycles in $K_9$

I am asked to find the number of distinct Hamiltonian cycles in the complete graph $K_9$ where no two of them have an edge in common. I came up with the following combinatorial argument but am very unsure about its validity. I confess part of this is borrowed from another proof I found online. Please help by spotting any errors.

Every pair of vertices in $K_9$ is adjacent. Hence any permutation on $V(K_9)$ can be considered to be representative of a Hamiltonian cycle. There are $9!$ such permutations. Since there are positions 9 from where one can begin the sequence and 2 possible directions in which one can travel the number of distinct Hamiltonian cycles is, $$N = \frac {9!} {9 * 2} = 4 * 7!$$

Now since we need the number of such cycles with no common edges,

Given the first two elements in the permutation there $7!$ ways to choose the rest all of which need to discarded. So for a given edge, $\bf e$ there $7!$ permutations of N which have $\bf e$ in common.

Therefore the required number is, $$M = \frac {N} {7!} = 4$$

Any help is appreciated.. Thanks..

• This seems like a good start, but you are overcounting (e.g., take two edges, what about the permutations which have both in common). – Igor Rivin Jan 6 '14 at 4:07

I can't follow your solution, but I also get $4$ as an answer. Here's how I figured it.

Consider a vertex $v$. There are $8$ edges meeting at $v$, and each Hamiltonian cycle uses two of them. If your Hamiltonian cycles have to be edge-disjoint, you can't have more than $4$ of them.

I still have to show that there exist $4$ edge-disjoint Hamiltonian cycles in $K_9$. I found these by trial and error. The vertices are numbered from $0$ to $8$.

0,1,2,3,4,5,6,7,8,0
0,2,4,6,8,1,3,5,7,0
0,3,8,5,2,7,4,1,6,0
0,4,8,2,6,3,7,1,5,0

• Thanks a lot. Nice argument. I am wondering if there is a way to prove the existence of 4 such cycles without drawing them out??.. – Ishfaaq Jan 6 '14 at 4:25
• @Ishfaaq I highly doubt it. However, there is a very simple way to draw the necessary cycles which is originally credited to Walecki in the 1890s. See math.stackexchange.com/questions/194247/… – Erick Wong Jan 6 '14 at 4:30

Actually, your answer is correct, but the reasoning is a little sketchy. Since each Hamiltonian cycle has $n$ edges, there can be at most $(n-1)/2$ edge-disjoint hamiltonian cycles. Now, how do you construct $(n-1)/2$ hamiltonian cycles?

• So the existence of 4 such cycles cannot be proven unless you actually illustrate them? – Ishfaaq Jan 6 '14 at 4:19
• I also tried using the algorithm to prove the existence of an Eulerian circuit for a graph with even vertices. But did not get far. – Ishfaaq Jan 6 '14 at 4:24