GATE CS 2025 Set 1 Q.64: Minimum Spanning Trees

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)

An undirected weighted complete graph on 4 vertices A (top-left), B (top-right), D (bottom-left), and C (bottom-right) with edge weights: (A, B) = 7, (A, D) = 6, (D, C) = 8, (B, C) = x, diagonal (B, D) = 1, and diagonal (A, C) = 3.

Your answer

Official answer and solution

Official answer: 5
From: Official GATE 2025 answer key

Solution

Find the minimum spanning tree of the graph without edge $(B, C)$ , identify the maximum edge weight on the unique path between $B$ and $C$ in that tree, and require $x$ to be strictly smaller.

Consider the graph without edge $(B, C)$ : its edges sorted by weight are $(B, D) = 1$ , $(A, C) = 3$ , $(A, D) = 6$ , $(A, B) = 7$ , and $(D, C) = 8$ .
By Kruskal's algorithm, the MST of $G \setminus \{(B, C)\}$ consists of the three edges: $(B, D) = 1, \quad (A, C) = 3, \quad (A, D) = 6$
Adding edge $(B, C)$ of weight $x$ to this tree creates the fundamental cycle $B - D - A - C - B$ , whose other edges have weights $1, 6,$ and $3$ (maximum weight $= 6$ ).
By the MST cycle property, edge $(B, C)$ is included in every MST of $G$ if and only if its weight $x$ is strictly less than the heaviest other edge in this cycle ( $x < 6$ , since at $x = 6$ there is a tie with $(A, D) = 6$ ).
Therefore, the maximum integer value of $x$ is 5.

Final answer

Common trap

Answering 6 by overlooking that the question requires $(B, C)$ to be included in every MST.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 64 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source