When the traveling salesman problem (Hamiltonian circuit) is applied to four cities, how many distinct tours are possible?
A) 3
B) 6
C) 12
D) 24

Question

Quizplus · Accepted Answer

For a traveling salesman problem with $n$ cities, the number of distinct tours (Hamiltonian circuits) is $(n-1)!$ because you can fix one city as a starting point (due to the tours being cyclic, any city can be the start), leaving $(n-1)$ cities to arrange in order. For $n=4$, this gives $(4-1)!=3!=6$ distinct tours.

When the Traveling Salesman Problem (Hamiltonian Circuit) Is Applied to Four