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)

graph on vertices A, B, C, D with edge weights A-B = 7, A-D = 6, D-C = 8, B-C = x, B-D = 1, A-C = 3.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 5

Explanation

Kruskal picks B-D (1) and A-C (3), giving components {B,D} and {A,C}. The cheapest other edges joining them are B-C (x) and A-D (6). B-C is in every MST only if x < 6, since at x=6 the tie allows A-D instead. The maximum integer is 5.