GATE 2025 CS1 Q.64: solution and answer

GATE 2025 · CS1Q.64 · 2 marks · NAT

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)

Graph (4 vertices A, B, C, D arranged as a square with both diagonals drawn, i.e. $K_{4}$ ):
- A connects to B with weight 7 (top edge)
- A connects to D with weight 6 (left edge)
- D connects to C with weight 8 (bottom edge)
- B connects to C with weight $x$ (right edge, unknown)
- B connects to D with weight 1 (one diagonal)
- A connects to C with weight 3 (other diagonal)

GATE 2025 CS1 question 64: A square-shaped graph with 4 labelled circular nodes: A (top-left), B (top-right), D (bottom-left), C (bottom-right). — Figure from the GATE 2025 CS1 paper. It is part of the question.

Answer and solution

ANSWER

The maximum integer value of x for which edge B–C lies in every minimum spanning tree is 5.

Official answer: 5Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)

Read the graph from the figure. It is $K_{4}$ on ${A, B, C, D}$ with $A B = 7$ , $A D = 6$ , $D C = 8$ , $B C = x$ , $B D = 1$ and $A C = 3$ .
The correct test for an edge being in EVERY minimum spanning tree: an edge $e$ is in every MST if and only if $e$ is not a maximum-weight edge (strict or tied) on any cycle. Equivalently, $e$ must be the strictly lightest edge crossing some cut. A tie for the maximum is not enough. If $e$ ties another edge for the heaviest weight on a cycle, you can swap $e$ for that edge and get another MST of the same weight that does not contain $e$ .
List every cycle through $B C$ and the largest of its other edges:
- $B - C - A - B$ (edges $C A = 3$ , $A B = 7$ ): largest is $7$ .
- $B - C - D - B$ (edges $C D = 8$ , $D B = 1$ ): largest is $8$ .
- $B - C - A - D - B$ (edges $C A = 3$ , $A D = 6$ , $D B = 1$ ): largest is $6$ .
- $B - C - D - A - B$ (edges $C D = 8$ , $D A = 6$ , $A B = 7$ ): largest is $8$ .
For $B C$ not to be a maximum on any of these cycles, $x$ must be strictly less than every one of these values:
$x < min (7, 8, 6, 8) = 6.$
The same condition from the cut side. Take the cut ${B, D}$ versus ${A, C}$ . The edges crossing it are $A B = 7$ , $A D = 6$ , $D C = 8$ and $B C = x$ . If $x < 6$ , then $B C$ is the unique lightest edge crossing this cut, so every MST must contain it (cut property).
Check $x = 6$ . Kruskal's algorithm takes $B D = 1$ , then $A C = 3$ , leaving the two components ${B, D}$ and ${A, C}$ . The next lightest edges are $A D = 6$ and $B C = 6$ , and either one joins the two components. So ${B D, A C, A D}$ and ${B D, A C, B C}$ are both MSTs of weight $10$ . The first one does not contain $B C$ , so $x = 6$ fails.
For any $x > 6$ , $B C$ is the strict unique maximum on cycle $B - C - A - D - B$ , so no MST contains it.
Check $x = 5$ . Kruskal's algorithm takes $B D = 1$ , $A C = 3$ , then $B C = 5$ , which joins ${B, D}$ and ${A, C}$ . All remaining edges ( $6, 7, 8$ ) would close a cycle. The MST ${B D, A C, B C}$ of weight $9$ is unique and contains $B C$ .
So $x$ must be an integer with $x < 6$ , and the maximum value is $x = 5$ .

KEY IDEA

An edge is in every MST exactly when it is the strictly lightest edge crossing some cut. Here that cut is {B, D} versus {A, C}. The other edges crossing it weigh 6, 7 and 8, so B–C must weigh strictly less than 6. The largest integer that works is 5.

WATCH OUT FOR

Treating a tie as good enough and answering 6. When x = 6, B–C ties with A–D = 6 across the cut {B, D} | {A, C}. Kruskal's algorithm can then pick A–D instead, which gives an MST without B–C. "Included in SOME MST" allows ties, but "included in EVERY MST" needs a strict inequality.

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2025 CS1 Q.64: solution and answer

Answer and solution

More Graph algorithms questions