GATE 2015 CS – Question 63
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ________.
[Graph: vertices A, B, C, D, E, F. MST edge weights: B-E = 15, B-C = 2, A-C = 9, E-F = 4, D-F = 6. The three remaining edges are A-B, C-D and D-E, with unknown weights.]
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 69
Explanation
Every edge outside the MST must weigh more than the heaviest edge on the MST path it closes. Edge A-B closes the path A-C-B, whose heaviest edge is 9, so it weighs at least 10. Edge C-D closes the path C-B-E-F-D, whose heaviest edge is 15, so it weighs at least 16. Edge D-E closes the path D-F-E, whose heaviest edge is 6, so it weighs at least 7. All 8 weights must be distinct, and 7, 10 and 16 are not used elsewhere. The minimum total is $36 + 7 + 10 + 16 = 69$.