Question 53

Given MST edges and weights:

• $(A, C) = 9$
• $(B, C) = 2$
• $(B, E) = 15$
• $(E, F) = 4$
• $(D, F) = 6$
  Sum of MST edge weights = $9 + 2 + 15 + 4 + 6 = 36$.

Non-MST edges:
The 3 non-MST edges are $(A, B)$, $(D, E)$, and $(C, D)$.
All 8 edge weights are distinct positive integers. The weights already used in the MST are $\{2, 4, 6, 9, 15\}$.

Cycle Property bounds:
For any non-MST edge $e = (u, v)$, its weight must be strictly greater than the maximum weight of any edge on the unique tree path between $u$ and $v$:

• Edge $(A, B)$:
  Tree path between $A$ and $B$: $A - C - B$. Edges have weights $9$ and $2$.

  $$w(A, B) > \max(9, 2) = 9.$$

  The smallest integer $> 9$ not in $\{2, 4, 6, 9, 15\}$ is $10$.
  Hence, minimum $w(A, B) = 10$.

• Edge $(D, E)$:
  Tree path between $D$ and $E$: $E - F - D$. Edges have weights $4$ and $6$.

  $$w(D, E) > \max(4, 6) = 6.$$

  The smallest integer $> 6$ not in $\{2, 4, 6, 9, 10, 15\}$ is $7$.
  Hence, minimum $w(D, E) = 7$.

• Edge $(C, D)$:
  Cut property: Consider the partition $\{A, B, C\}$ and $\{D, E, F\}$. The cut edges are $(B, E)$ and $(C, D)$.
  Since $(B, E) = 15$ is in the MST, $(B, E)$ must be the strictly lightest edge crossing this cut.
  Therefore, $w(C, D) > 15$.
  The smallest integer $> 15$ is $16$.
  Hence, minimum $w(C, D) = 16$.

Minimum Total Weight: