GATE 2025 CS (CS1) – Question 64
The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is _________ . (answer in integer)

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5
Explanation
For the edge $B$–$C$ with weight $x$ to be in **every** MST, it must be strictly lighter than every other edge that could replace it.
Kruskal's algorithm: take $B$–$D$ (1) and $A$–$C$ (3). These two edges give components $\{B,D\}$ and $\{A,C\}$. To join the two components we have the candidates $B$–$C$ ($x$), $A$–$D$ (6), $A$–$B$ (7) and $D$–$C$ (8). The cheapest connecting edge goes into the MST.
If $x<6$, $B$–$C$ is the unique cheapest and is in the MST. If $x=6$, there is a tie with $A$–$D$, and an MST can use $A$–$D$ instead, so $B$–$C$ is not in every MST.
The largest integer value with $x<6$ is $\mathbf{5}$.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2025 CS (CS2) Q29
- GATE 2025 CS (CS2) Q37
- GATE 2025 CS (CS2) Q59
- GATE 2024 CS (CS1) Q45
- GATE 2024 CS (CS1) Q60
- GATE 2024 CS (CS2) Q59
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →