GATE 2018 CS – Question 57
Consider the following undirected graph G (the edge weights are shown in the figure, with one edge of unknown weight $x$):
Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of $x$ is ________.

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 4
Explanation
Name the top, upper-left, lower-left, lower-right and upper-right vertices A,B,C,D,E. The weight-1 edge AC and weight-3 edge AD are cheaper than the alternatives needed to connect their components, so both occur in every minimum spanning tree.
Vertex B can attach through AB or BC, both of weight 4, giving two choices. Vertex E can attach through AE of weight x or DE of weight 5. Setting **x=5** makes these two alternatives equally cheap, without creating a cheaper replacement for AC or AD.
The choices are independent, giving $2\times2=\boxed4$ minimum spanning trees, each of weight 13. If x differs from 5, E has only one cheapest attachment, reducing the count.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2015 CS (CS1) Q51
- GATE 2015 CS (CS1) Q63
- GATE 2016 CS (CS1) Q21
- GATE 2016 CS (CS1) Q24
- GATE 2016 CS (CS1) Q48
- GATE 2016 CS (CS1) Q49
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →