GATE 2015 CS (CS1) – 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
The MST has weight $15+2+9+4+6=36$, using edges $B$–$E$ (15), $B$–$C$ (2), $A$–$C$ (9), $E$–$F$ (4) and $D$–$F$ (6). Every non-tree edge must weigh **more** than the heaviest edge on the tree path it closes (otherwise it would replace that edge in an MST). All 8 weights must be distinct integers.
- $A$–$B$ closes the path $A$–$C$–$B$ (weights 9, 2): needs weight $>9$, so at least **10**.
- $C$–$D$ closes the path $C$–$B$–$E$–$F$–$D$ (weights 2, 15, 4, 6): needs weight $>15$, so at least **16**.
- $D$–$E$ closes the path $D$–$F$–$E$ (weights 6, 4): needs weight $>6$, so at least **7**.
These minimums (10, 16, 7) are distinct from each other and from the tree weights, so they can all be used at once: $10+16+7=33$.
Smallest possible total $=36+33=\mathbf{69}$.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2016 CS (CS1) Q21
- GATE 2016 CS (CS1) Q24
- GATE 2016 CS (CS1) Q48
- GATE 2016 CS (CS1) Q49
- GATE 2016 CS (CS1) Q50
- GATE 2017 CS (CS1) Q36
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →