0
$\begingroup$

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..

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

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

$\endgroup$
  • $\begingroup$ 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??.. $\endgroup$ – Ishfaaq Jan 6 '14 at 4:25
  • 1
    $\begingroup$ @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/… $\endgroup$ – Erick Wong Jan 6 '14 at 4:30
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So the existence of 4 such cycles cannot be proven unless you actually illustrate them? $\endgroup$ – Ishfaaq Jan 6 '14 at 4:19
  • $\begingroup$ 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. $\endgroup$ – Ishfaaq Jan 6 '14 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.