GATE CS 2025 Set 1 Q54 — Minimum Spanning Trees

According to the Cycle Property of Minimum Spanning Trees (MSTs), an edge $e$ is included in every MST of a graph if and only if, for every cycle $C$ containing $e$, the weight of $e$ is strictly less than the maximum weight of the remaining edges in $C$.

This is equivalent to stating that the weight of the edge $BC$ (which is $x$) must be strictly less than the bottleneck (the maximum edge weight) of any alternative path between $B$ and $C$ in the graph $G \setminus \{BC\}$:

Let us analyze the alternative paths between $B$ and $C$ in $G \setminus \{BC\}$ and find their bottlenecks:

• Path 1: $B \to D \to C$
  Edges: $\{BD, DC\}$ with weights $\{2, 6\}$.
  Bottleneck = $\max(2, 6) = 6$.
• Path 2: $B \to D \to E \to C$
  Edges: $\{BD, DE, EC\}$ with weights $\{2, 7, 5\}$.
  Bottleneck = $\max(2, 7, 5) = 7$.
• Path 3: $B \to A \to D \to C$
  Edges: $\{BA, AD, DC\}$ with weights $\{3, 4, 6\}$.
  Bottleneck = $\max(3, 4, 6) = 6$.

The minimum bottleneck among all alternative paths is $6$. Therefore, for the edge $BC$ to be present in every MST, we must have:

Since $x$ must be an integer, the maximum possible value of $x$ is 5.