The number of distinct minimum-weight spanning trees of the following graph is ________

We use Kruskal's algorithm to find the number of distinct minimum spanning trees (MSTs):

1. Graph properties:

   • Vertices: $V = \{a, b, c, d, e, f, g\}$, so $|V| = 7$.

   • Any spanning tree must contain $|V| - 1 = 6$ edges.

2. Edges of weight 1:

   • Edges: $(a, b), (a, f), (c, d), (e, d)$.

   • None of these 4 edges form a cycle.

   • Therefore, all 4 edges must be selected in any MST.

   • After including these edges, we have 3 connected components:

     $$\{a, b, f\}, \quad \{c, d, e\}, \quad \{g\}$$

3. Edges of weight 2:

   • Edges connecting component $\{a, b, f\}$ to vertex $g$: $(a, g), (b, g), (f, g)$ (3 choices).

   • Edges connecting component $\{c, d, e\}$ to vertex $g$: $(c, g), (d, g), (e, g)$ (3 choices).

   • To connect all 3 components into a single connected tree, we need exactly 2 more edges of weight 2:

     • One edge from $\{(a, g), (b, g), (f, g)\}$

     • One edge from $\{(c, g), (d, g), (e, g)\}$

4. Total number of MSTs:

   $$\text{Number of distinct MSTs} = 3 \times 3 = 9$$

All selected trees will have the same minimum total weight: $4(1) + 2(2) = 8$.