The GATE Grind

GATE 2025 CS (CS1) – Question 64

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

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)

Diagram for GATE 2025 CS (CS1) question 64

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

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →