0

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?

Priyanshul Govil
  • 133
  • 2
    Consider the complete graph on vertices ${1,2,3,4}$. Are $1 \sim 2 \sim 3 \sim 1$ and $2 \sim 3 \sim 1 \sim 2$ the same circuit, or different? – Matthew Leingang Jun 23 '21 at 17:02
  • @MatthewLeingang That is the same circuit, but I'm still a bit confused as to why this works. 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$. – Priyanshul Govil Jun 23 '21 at 17:12
  • 1
    Okay, I think I understand now. My above case is incorrect. $2 \sim 1 \sim 3 \sim 2$ 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$. – Priyanshul Govil Jun 23 '21 at 17:18
  • 1
    You got it. Your 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)!$. – Matthew Leingang Jun 23 '21 at 17:26
  • 1
    You can answer your own question now, and accept your answer, so that the question does not remain on the unanswered queue. (or you can delete the question) – Ethan Bolker Jun 23 '21 at 18:00
  • @EthanBolker done! – Priyanshul Govil Jun 23 '21 at 19:35

1 Answers1

2

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)!$
Priyanshul Govil
  • 133