12.9 Exercise 3

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

1. Use the formula $\left(n - 1\right) !$ to calculate the number of distinct Hamilton cycles in the graph.
2. Use the formula $\frac{\left(n - 1\right) !}{2}$ to calculate the greatest number of different weights possible for the Hamilton cycles.
3. 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
4. Which pairs of cycles must have the same weights? How do you know?