GATE CS 2026 Set 1 Q.49: Minimum Spanning Trees

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?

In every cycle $C$ of $G$ , the edge with the largest weight in $C$ is not in any MST

In every cycle $C$ of $G$ , the edge with the smallest weight in $C$ is in every MST

For every vertex $v \in V$ , the edge with the largest weight incident on $v$ is not in any MST

For every vertex $v \in V$ , the edge with the smallest weight incident on $v$ is in every MST

Official answer and solution

Solution

Apply the Cycle Property (heaviest edge in a cycle) and Cut Property (lightest edge across the cut $(\{v\}, V \setminus \{v\})$ ).

Option (A) is true: By the Cycle Property (with distinct edge weights), the unique heaviest edge in any cycle $C$ cannot belong to any MST.
Option (B) is false: The lightest edge $e$ in a cycle $C$ can simultaneously be the heaviest edge in another cycle $C'$ , in which case $e$ is excluded from the MST.
Option (C) is false: If a vertex $v$ has degree $1$ , its single incident edge is the heaviest edge incident on $v$ yet must be included in every spanning tree.
Option (D) is true: Considering the cut $(\{v\}, V \setminus \{v\})$ for any vertex $v \in V$ , the Cut Property guarantees that the unique lightest edge crossing this cut (the smallest-weight edge incident on $v$ ) belongs to every MST.

Final answer

Options (A), (D)

Common trap

Confusing the cycle property (which excludes the heaviest edge of a cycle) with including the lightest edge of a cycle.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 49 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.