GATE2025_CS1_Q64

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)

✅ Final Answer:

The correct answer is 5.

🔹 Short Answer:

For edge (B,C) to be in *every* MST, its weight 'x' must be strictly less than the bottleneck (heaviest edge) of any alternative path between B and C. The alternative paths and their bottlenecks are: B-A-C (bottleneck 7), B-D-C (bottleneck 8), and B-D-A-C (bottleneck 6). To satisfy all conditions, 'x' must be less than the minimum of these bottlenecks, so `x < min(7, 8, 6)`. This simplifies to `x < 6`. The maximum integer value for 'x' that satisfies this is 5.

🔸 Long Answer:

This problem is solved by applying the **Cycle Property of Minimum Spanning Trees**. This property is a cornerstone of MST theory and provides a definitive way to determine if an edge must be in every MST.

The Cycle Property

An edge e is guaranteed to be in every MST of a graph if, for any cycle it is a part of, its weight is strictly less than the weight of the heaviest other edge in that cycle. In other words, its weight must be strictly less than the bottleneck of any alternative path between its two endpoints.

Step 1: Identify Cycles Containing Edge (B, C)

We need to find all simple cycles in the graph that include the edge (B, C). This is equivalent to finding all paths between B and C that do not use the edge (B,C) itself.

Let's analyze the paths from B to C:

• Path 1: B → A → C
  This path consists of edges (B,A) with weight 7 and (A,C) with weight 1. The heaviest edge (bottleneck) on this path is 7.
• Path 2: B → D → C
  This path consists of edges (B,D) with weight 3 and (D,C) with weight 8. The heaviest edge on this path is 8.
• Path 3: B → D → A → C
  This path consists of edges (B,D) with weight 3, (D,A) with weight 6, and (A,C) with weight 1. The heaviest edge on this path is 6.

Step 2: Apply the Cycle Property to Each Cycle

For edge (B,C) with weight `x` to be in every MST, `x` must be strictly smaller than the bottleneck of each of these alternative paths.

Cycle	Alternative Path (B to C)	Heaviest Edge on Path (Bottleneck)	Condition on x
B-A-C-B	B → A → C	7	x < 7
B-D-C-B	B → D → C	8	x < 8
B-D-A-C-B	B → D → A → C	6	x < 6

Step 3: Find the Most Restrictive Condition

To ensure `x` is included in all MSTs, it must satisfy all the derived conditions simultaneously:

x < 7    AND    x < 8    AND    x < 6

The intersection of these conditions is the most restrictive one, which is x < 6.

Step 4: Determine the Maximum Integer Value for x

We must find the maximum integer `x` that satisfies x < 6. If `x` were 6, it would tie with the edge (A,D). Kruskal's algorithm could pick edge (A,D) first, potentially creating an MST that doesn't include (B,C). To guarantee inclusion in *every* MST, the weight must be strictly less.
The largest integer strictly less than 6 is 5.

Bibliography:
- Cormen, T. H., et al. (2009). Introduction to Algorithms. MIT Press. (Chapter 23: Minimum Spanning Trees).
- Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson. (Chapter 4: Greedy Algorithms, Cut Property and Cycle Property).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.