The GATE Grind

GATE 2026 CS (CS1) – Question 49

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple select

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?

  1. In every cycle $C$ of $G$, the edge with the largest weight in $C$ is not in any MST
  2. In every cycle $C$ of $G$, the edge with the smallest weight in $C$ is in every MST
  3. For every vertex $v \in V$, the edge with the largest weight incident on $v$ is not in any MST
  4. For every vertex $v \in V$, the edge with the smallest weight incident on $v$ is in every MST

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) In every cycle $C$ of $G$, the edge with the largest weight in $C$ 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

Explanation

Since all edge weights are unique, $G$ has a unique MST.
- **(A) is true (Cycle Property)**: For any cycle $C$ in $G$, if $e$ is the strictly heaviest edge in $C$, removing $e$ from any spanning tree containing it and replacing it with another edge from $C$ yields a spanning tree of strictly smaller weight. Hence, the strictly heaviest edge of any cycle can never belong to an MST.
- **(B) is false**: The lightest edge in a cycle is not guaranteed to be in the MST if other edges connecting the components have smaller weights.
- **(C) is false**: The heaviest edge incident on a vertex $v$ can be the ONLY edge connecting $v$ to the rest of the graph (a bridge / cut-edge), in which case it must be included in every spanning tree.
- **(D) is true (Cut Property)**: For any vertex $v$, consider the cut $( \{v\}, V \setminus \{v\} )$. The edges crossing this cut are precisely the edges incident on $v$. By the Cut Property, the minimum-weight edge crossing any cut must belong to the MST.

Therefore, statements (A) and (D) are true.