Let \(G\) be a connected undirected graph of 100 vertices and 300 edges. The…
2015
Let \(G\) be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of \(G\) is 500. When the weight of each edge of \(G\) is increased by five, the weight of a minimum spanning tree becomes ________.
Attempted by 131 students.
Show answer & explanation
Correct answer: 995
Key insight: A minimum spanning tree for a connected graph with n vertices has exactly n - 1 edges, so increasing every edge weight adds the same constant to each edge of the tree.
Step 1: The graph has 100 vertices, so any spanning tree has 100 - 1 = 99 edges.
Step 2: Increasing the weight of each edge by 5 increases the total weight of any spanning tree by 99 × 5 = 495.
Step 3: The original minimum spanning tree weight was 500, so the new minimum spanning tree weight is 500 + 495 = 995.
Answer: 995
A video solution is available for this question — log in and enroll to watch it.