Traveling Salesperson Problem · Example 2

Suppose you have a complete weighted graph with vertices N, M, O, and P.

(a) Use the formula $\left(n-1\right)!$ to calculate the number of distinct Hamilton cycles in the graph.
(b) Use the formula $\frac{\left(n-1\right)!}{2}$ to calculate the greatest number of different weights possible for the Hamilton cycles.
(c) Are all of the distinct Hamilton cycles listed here? How do you know?
Cycle 1: N → M → O → P → N
Cycle 2: N → M → P → O → N
Cycle 3: N → O → M → P → N
Cycle 4: N → O → P → M → N
Cycle 5: N → P → M → O → N
Cycle 6: N → P → O → M → N
(d) Which pairs of cycles must have the same weights? How do you know?

OpenStax, Contemporary Mathematics · §12.9 Traveling Salesperson Problem · Example 2