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.


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

  • $\begingroup$ That is if n> 2. $\endgroup$
    – gnasher729
    Jan 17, 2017 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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