Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry…
2010
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
W = \(\begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\ 1 & 0 & 12 & 4 & 9 \\ 8 & 12 & 0 & 7 & 3 \\ 1 & 4 & 7 & 0 & 2 \\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}\)
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
- A.
7
- B.
8
- C.
9
- D.
10
Attempted by 95 students.
Show answer & explanation
Correct answer: D
Final answer: 10
Key idea: If vertex 0 is a leaf it connects to exactly one other vertex. The remaining vertices {1,2,3,4} must form a spanning tree on their own. So the minimum total weight equals the minimum spanning tree weight on {1,2,3,4} plus the smallest edge from 0 to {1,2,3,4}.
List edges among vertices 1–4 (weights): 1–3: 4, 1–4: 9, 1–2: 12, 2–3: 7, 2–4: 3, 3–4: 2.
Compute an MST on {1,2,3,4} (Kruskal): pick edge 3–4 (2), then 2–4 (3), then 1–3 (4). These three edges connect all four vertices with total weight 2 + 3 + 4 = 9.
Find the smallest edge from vertex 0 to the rest: edges from 0 are 0–1:1, 0–3:1, 0–4:4, 0–2:8. The minimum is 1 (connect to vertex 1 or vertex 3).
Add that smallest edge to the MST of {1,2,3,4}: total weight = 9 + 1 = 10. Example spanning tree achieving 10: edges 0–1 (1), 1–3 (4), 3–4 (2), 2–4 (3).
Conclusion: The minimum possible weight of a spanning tree in which vertex 0 is a leaf is 10, and no smaller total is possible because the MST of {1,2,3,4} already costs 9 and attaching vertex 0 requires at least one additional unit of weight.