Correct : 5
The correct answer is 5.
For an edge to appear in every MST, its weight must be strictly less than the bottleneck of every alternative path connecting the same two nodes. The bottleneck of a path is the maximum edge weight along that path.
Let"s check all simple paths from B to C (other than the direct edge BC = x):
• Path B → A → C: edges 7 and 1 → bottleneck = 7
• Path B → D → C: edges 3 and 8 → bottleneck = 8
• Path B → D → A → C: edges 3, 6, and 1 → bottleneck = 6
The minimum of these bottlenecks is 6 (from path B→D→A→C).
For edge BC to be forced into every MST, its weight x must be strictly less than 6. If x = 6, Kruskal"s algorithm could skip BC and use the path B→D→A→C instead — so BC would not be in every MST.
The largest integer satisfying x < 6 is x = 5.
Similar Questions
Total Unique Visitors