Show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem on $n$ points?

Question

The question is to show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem (ETSP) on $n$ points.

My attempt was using induction. So I start by:

• If $n=3$, then we have a triangle and there is only one tour.

• Assume that there are $(n-1)!/2$ distinct tours for a ETSP on $n$ points. Prove that there are $n!/2$ distinct tours for a ETSP on $n+1$ points?

  • Here I proceed like this:

    • for each tour $t$ from the $(n-1)!/2$ distinct tours do: add one point $n+1$.

    • for each edge $e=\{v_i, v_j\}$ in $t$ do: remove $e$ and create two edges $e_1=\{n+1,v_i\}$ and $e_2=\{n+1, v_j\}$. We have a new tour and in total we can create $n$ distinct tours.

      Since there are $(n-1)!/2$ distinct tours, we will have $n(n-1)!/2=n!/2$ distinct tours.

This gives the desired result but somehow long and complicated.

Answer 1

We may reason in a combinatorial way.

There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on any of the $n$ nodes, and we may choose the direction in $2$ ways. Therefore, each tour was counted a total of $2n$ times.

This yields the desired result.