Minimum Spanning Trees

The diagonals BD and AC (weights 1 and 3) are in every MST: BD is the unique lightest edge at D (DA = 6, DC = 8) and AC is the unique lightest edge at A (AD = 6, AB = 7). Together they form two pieces, {A, C} and {B, D}.

A spanning tree on 4 vertices has 3 edges, so exactly one more edge must join the two pieces. The candidates are BC = \(x\), AD = 6, AB = 7 and CD = 8. BC is in every MST only if it is strictly the lightest of these, i.e. \(x \lt 6\).

At \(x = 6\), BC ties with AD and {BD, AC, AD} is an MST without BC. So the largest integer value is 5.

Answer: 5

MSTs stay. Every spanning tree of a connected graph with \(n\) vertices has exactly \(n - 1\) edges, so every spanning tree gets heavier by the same amount, \((n - 1)\alpha\). Their order by weight does not change, so every MST remains an MST.

SPs can change. A path with \(k\) edges gets heavier by \(k\alpha\), so paths with more edges are penalised more. Take edges \(uv\) and \(vw\) of weight 1 and an edge \(uw\) of weight 3. The shortest path from \(u\) to \(w\) is \(u, v, w\) with weight 2. After adding \(\alpha = 2\) it weighs 6, while the single edge \(uw\) weighs 5, so the old SP is no longer shortest.

Answer: C

Think of Kruskal’s algorithm, which takes the cheapest edges first.

• The four weight-1 edges \(ab, af, cd, de\) form no cycle, so every minimum spanning tree contains them. They leave three components: \(\{a, b, f\}\), \(\{c, d, e\}\) and \(\{g\}\).
• Two more edges are needed, and all weight-2 edges meet \(g\): \(ga, gb, gf\) reach the first component and \(gc, gd, ge\) the second. A tree takes exactly one from each group, since two from the same group would close a cycle.
• The weight-3 edges are never used.

So there are \(3 \times 3 = 9\) minimum spanning trees, each of weight 8.

Answer: 9