Skip to content
GATEiit

GATE CSE 2025 Session 1 Q64: Largest x keeping edge BC in every MST

Question

The maximum value of xx 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 A, B, C, D: edges A–B weight 7, A–D weight 6, D–C weight 8, B–C weight x, and the diagonals B–D weight 1 and A–C weight 3
Tap the figure to enlarge

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 5 (official GATE 2025 final answer key)

Concept used: Cycle property: an edge is in every MST iff it is strictly lighter than the heaviest edge on every cycle-closing alternative path.

First step: Without B–C, the cheapest B-to-C connection in an MST is B–D (1), D–A (6), A–C (3); B–C must be strictly lighter than the 6 on this path.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 1 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2025 Session 1 questions →