Why are the total (non-distinct) Hamiltonian circuits in complete graph $K_n$ $=$ $(n−1)!$

graph theoryhamiltonian-path

I came across this answer on a very similar question which says:

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.

I have seen many textbooks which mention the exact same reasoning, but what I do not understand is the fixed choice of the starting vertex.

Since the starting vertex itself can be chosen in $n$ ways, we should have $n!$ total Hamiltonian circuits and not $(n-1)!$.

Why is this not the case?

Best Answer

I will try to merge my discussion with Matthew Leingang in the comments into an answer.

Consider the complete graph on vertices $\{1,2,3\}$. Here $1 \sim 2 \sim 3 \sim 1$ and $2 \sim 3 \sim 1 \sim 2$ are equivalent circuits.

Now, why does it work?

Say our starting vertex is $1$ and we either select the edge to $2$ or $3$. Without the loss of generality, let's say we select $1 \sim 2$. Now we have a circuit which is $1 \sim 2 \sim 3 \sim 1$.

Now, what would happen if we didn't have starting vertex as $1$? We could've had a circuit $2 \sim 1 \sim 3 \sim 2$. However, this is equivalent to $1 \sim 3 \sim 2 \sim 1$ which would've been there had we considered the first edge to be $1 \sim 3$.

Conclusion

The method of choosing an initial vertex first will count each circuit $n$ times instead of once. So, the total number of distinct circuits is:

$n!$ $/$ $n$ $=$ $(n−1)!$

Related Solutions

[Math] Number of Hamiltonian Paths on a (in)complete graph

This looks a lot like the way you determine the chromatic polynomial, but in a some sense "reversed": you know the values of your most "complicated" graphs instead of iterating until you have reached the simplest ones.

Consider one edge $e$, then the number of hamiltonian cycles in $G$ equals the number of cycles in $G-e$ (those that do NOT use the edge) plus the number of cycles in $G/e$ (those that DO use the edge).

This can be transformed into a recursive algorithm: you know the values for the complete graphs, and all other intermediate values you require are the result of removing a smaller list of edges from a smaller complete graph.

However this will not perform at all on anything but the smallest examples and it certainly will not give you anything like a closed formula for the number of hamiltonian cycles. I am not at all sure if this is an acceptable solution.

EDITED AFTER REQUEST FOR DETAILS:

Consider next pseudocode.

int function h(int n, List l)
{
  if (l is empty) { return number of hamilton cycles in K_n }
  create new list lNew;
  return h(n, l minus last element) - h(n - 1, lNew);
}

This function $h$ calculates the number of hamiltonian cycles in $K_n$ when the edges of the list $l$ are missing. You use the recurrence $h(G-e)=h(G)-h(G/e)$, so you repeatedly put one edge back into the graph until you have put back everything. You have to decide on how to represent the edges on the list. One option is to represent each edge on $l$ simply as a pair of numbers in the range $1..n$. The only tricky part is the creation of the list $lNew$. You cannot just copy its elements from the list $l$, since they refer to edges of a $K_{n-1}$ after the recursion, so depending on the edge you are removing you need to manipulate the list elements.

I have no clue how this will perform with the numbers you mention. The most important thing will be that the list of edges is not too long, since that will determine the depth of the recursion. Be sure to use some kind of 'big integer' arithmetic or find other ways to avoid large numbers.

[Math] How many Hamiltonian cycles are there in a complete graph that must contain certain edges

The question can be interpreted as asking how many ways there are to construct a Hamiltonian cycle under these constraints. Since we know $\{1,2\}$ must be in the cycle, it seems reasonable to assume that we start at vertex $1$ and the first edge traversed is $\{1,2\}$. From here, the rest of the cycle is given by a permutation of the remaining vertices $\{3,4, \dots, n\}$ under the constraint that 3 and 4 have to be consecutive. Similar to your idea of treating $\{3,4\}$ as a single vertex, we can permute these $n-3$ objects ($n$ vertices, minus the two we already used and treating 3 and 4 as a single unit) in $(n-3)!$ ways. Then there are 2 orientations for the $\{3,4\}$ edge, so we multiply to get a total of $2(n-3)!$ Hamiltonian cycles.

In your example, we do indeed get $2(5-3)! = 4$ such Hamiltonian cycles.

As a side note, you can generalize this result. If the $k$ "fixed edges" comprise $p$ vertex-disjoint paths, then the number of Hamiltonian cycles should be $2^{p-1}(n-k-1)!$. There's $p-1$ paths to orient, $n - k - p$ vertices which are still on their own, and $p-1$ paths to place as a single unit somewhere in the permutation (so we permute $n-k-1$ objects in this step).