Question 59

The graph has $|V| = 7$ vertices, so any spanning tree contains $|V| - 1 = 6$ edges:

1. Weight-1 edges: There are $4$ edges of weight $1$: $(a, b), (a, f), (c, d), (e, d)$. They form no cycles, so all $4$ must be in every MST. Including them partitions the vertices into $3$ connected components:
   $$C_1 = \{a, b, f\}, \quad C_2 = \{g\}, \quad C_3 = \{c, d, e\}$$
2. Weight-2 edges: To connect the $3$ components $C_1, C_2, C_3$ using $2$ additional edges of minimum weight ($2$):
   • We must pick exactly $1$ of the $3$ weight-2 edges between $C_1$ and $g$: $(a, g), (b, g),$ or $(f, g)$ (3 choices).
   • We must pick exactly $1$ of the $3$ weight-2 edges between $C_3$ and $g$: $(c, g), (d, g),$ or $(e, g)$ (3 choices).

Therefore, the number of distinct minimum-weight spanning trees is $3 \times 3 = 9$ (each of weight $4 \times 1 + 2 \times 2 = 8$).