GATE 2026 CS1 Q.49: solution and answer

GATE 2026 · CS1Q.49 · 2 marks · MSQ

Let $G (V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

(A)
In every cycle $C$ of $G$ , the edge with the largest weight in $C$ is not in any MST
(B)
In every cycle $C$ of $G$ , the edge with the smallest weight in $C$ is in every MST
(C)
For every vertex $v \in V$ , the edge with the largest weight incident on $v$ is not in any MST
(D)
For every vertex $v \in V$ , the edge with the smallest weight incident on $v$ is in every MST

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

A;D — Statements A and D are true (the maximum-weight edge in any cycle is excluded from every MST by the cycle property; the minimum-weight edge incident on any vertex is included in every MST by the cut property applied to the trivial cut {v}). B and C are false.

Official answer: A, DSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Since all edge weights in $G$ are distinct, $G$ has a unique MST, and both the cycle property and the cut property hold in their strict (no-tie) form.
Cycle property (Statement A): In any cycle $C$ , let $e$ be the strictly maximum-weight edge in $C$ . If $e$ were in some spanning tree $T$ , removing $e$ splits $T$ into two components; since $e$ lies on a cycle, some other edge $f$ of $C$ (with $f \neq = e$ ) crosses back between these two components. Replacing $e$ with $f$ gives another spanning tree that is no heavier, and strictly lighter because weights are unique — so $T$ was not minimum. Hence the max-weight edge of every cycle is excluded from every MST: Statement A is TRUE.
Testing Statement B with a counterexample: Take vertices $v_{1}, v_{2}, v_{3}, v_{4}$ with edges $v_{1} v_{4} = 1$ , $v_{2} v_{4} = 1$ , $v_{1} v_{2} = 3$ , $v_{2} v_{3} = 4$ , $v_{1} v_{3} = 5$ . The cycle $v_{1}$ - $v_{2}$ - $v_{3}$ - $v_{1}$ has weights ${3, 4, 5}$ , so its minimum-weight edge is $v_{1} v_{2}$ (weight 3).
Running Kruskal's algorithm (edges in increasing order $1, 1, 3, 4, 5$ ): add $v_{1} v_{4}$ ; add $v_{2} v_{4}$ (now ${v_{1}, v_{2}, v_{4}}$ connected); skip $v_{1} v_{2}$ since it would close a cycle; add $v_{2} v_{3}$ to connect $v_{3}$ . The unique MST is ${v_{1} v_{4}, v_{2} v_{4}, v_{2} v_{3}}$ , which does not contain $v_{1} v_{2}$ — the minimum edge of that cycle. So a cycle's minimum edge need not be in the MST: Statement B is FALSE.
Testing Statement C: Take any vertex $v$ of degree 1 (a leaf), for instance in a simple path graph. Its single incident edge is simultaneously the largest- and smallest-weight edge incident on it. Since removing this edge would disconnect $v$ from the rest of the graph, this edge must belong to every spanning tree, including the MST — so the 'largest incident edge' at $v$ IS in the MST, contradicting the claim that it is in no MST: Statement C is FALSE.
Cut property (used for Statement D): For any cut $(S, V ∖ S)$ , if $e$ is the strictly minimum-weight edge crossing the cut, then $e$ lies in every MST — any spanning tree lacking $e$ can be improved by swapping in $e$ for some heavier crossing edge that its addition would make redundant.
Statement D: Apply the cut property to the trivial cut $({v}, V ∖ {v})$ for an arbitrary vertex $v$ . The edges crossing this cut are exactly the edges incident on $v$ . Therefore the minimum-weight edge incident on $v$ is the unique minimum-weight crossing edge of this cut, and by the cut property it must lie in every MST. Since $v$ was arbitrary, this holds for every vertex: Statement D is TRUE. (This is also the principle behind Borůvka's algorithm, where each component picks its own cheapest outgoing edge.)
Hence the true statements are A and D.

KEY IDEA

Because all edge weights are unique, $G$ has a unique MST, and two classical results pin down every option: the cycle property (in any cycle, the strictly max-weight edge is never in an MST) and the cut property (across any cut, the strictly min-weight crossing edge is in every MST). Applying the cut property to the trivial cut $({v}, V ∖ {v})$ — whose crossing edges are exactly $v$ 's incident edges — shows the minimum edge at each vertex is forced into every MST.

WATCH OUT FOR

Confusing "every cycle's minimum edge is safe/must be in the MST" (false — it can be excluded once a cheaper path already connects its endpoints, as Kruskal shows) with the correct cut-property statement about a vertex's minimum incident edge; and assuming an edge's local extremal property (largest/smallest at a vertex) behaves symmetrically to its extremal property in a cycle, when cycles and cuts are genuinely dual/opposite structures in MST theory.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2026 CS1 Q.49: solution and answer

Answer and solution

More Graph algorithms questions