How many Hamiltonian cycles are there in a complete graph $K_n$ ($n\geq 3$) Why?

It seems to me like the answer should be $n!$. Since you can first select the first vertex, then select each remaining vertex until you've got them all in a permutation.

My textbook, however, says that the answer is $(1/2)(n-1)!$

Unfortunately, it doesn't explain why this is. Why is it?

Solution 1:

The answer really depends on how we think that two Hamiltonian cycles are equal. Take $K_3$ as example. Let's call its vertices $1$, $2$ and $3$. Then do we consider $1\to2\to3\to1$ same as $2\to3\to1\to 2$? If yes, $1\to2\to3\to1$ is the same as $2\to3\to1\to 2$, which is the same as $3\to1\to2\to 3$ in $K_3$. Then we will have two Hamiltonian cycles $1\to 2\to3\to1$ and $1\to 3\to 2\to1$. Moreover, if we consider $1\to 2\to3\to1$ and $1\to 3\to 2\to1$ being the same because the second one is obtained by reversing direction the first one, then we have only one Hamiltonian cycle in $K_3$.

For general $K_n$, it's the same. $1\to2\to\cdots\to n\to1$ is the same as $2\to\cdots\to n\to1\to 2$ is the same as.... $n\to1\to 2\to\cdots \to n$. And the $1\to 2\to\cdots\to n\to1$ and $1\to n\to\cdots\to2\to1$ being the same because the second one is obtained by reversing direction the first one. So we have altogether $\frac{1}{2}(n-1)!$ Hamiltonian cycles in $K_n$.

Solution 2:

Just bringing in all related similar numbers of Hamiltonian circuits in complete graphs with possible intuitive interpretation of them:

Total (non-distinct) Hamiltonian circuits in complete graph $K_n$ is $(n-1)!$

This follows from the fact that starting from any vertex we have $n-1$ edges to choose from first vertex, $n-2$ edges to choose from second vertex, $n-3$ to choose from the third and so on. These being independent choices, we get $(n-1)!$ possible number of choices.

Number of distinct not edge disjoint Hamiltonian circuits in complete graph $K_n$ is $\frac{(n-1)!}{2}$

Above number ($(n-1)!$) is divided by $2$, because each Hamiltonian circuit has been counted twice (in reverse direction of each other like these: $A\rightarrow B \rightarrow C \rightarrow A$ and $A\rightarrow C \rightarrow B \rightarrow A$).

Number of edge disjoint Hamiltonian circuits in complete graph $K_n$ where $n$ is odd is $\frac{n-1}{2}$

We can realize this by arranging the vertices inside the circle as follows:

There is only single edge connecting two vertices in upper half of circumference. Each such edge can lead to unique edge disjoint Hamiltonian circuit. We can rotate this circuit so that this edge gets mapped to the next pair of vertices on the upper half of the circumference which will lead to next unique edge disjoint Hamiltonian circuit. There are $\frac{n-1}{2}$ such consecutive pairs in the upper half of the circumference with $\frac{n-1}{2}$ edges connecting them each leading to unique edge disjoint Hamiltonian circuits.

Solution 3:

I can see why you would think that. For n=5 (say a,b,c,d,e) there are in fact n! unique permutations of those letters.

However, the number of cycles of a graph is different from the number of permutations in a string, because of duplicates -- there are many different permutations that generate the same identical cycle.

There are two forms of duplicates:

First, in a cycle there is no starting and ending place. That means that permutation a-b-c-d-e would generate the same cycle as b-c-d-e-a, c-d-e-a-b, d-e-a-b-c and e-a-b-c-d. Notice that there are n duplicate tours in the above, that's where the (n-1)! instead of n! comes from.

Second, in a cycle, direction doesn't matter. That means that permutations a-b-c-d-e and e-d-c-b-a would generate the same cycle. For every permutation, there is exactly one permutation that is it's reverse. That's where the /2 comes from.

Thus, (n-1)!/2 unique cycles.