What are common examiner traps in Minimum Spanning Trees?

Assuming the lightest edge in a cycle must be in the MST (it can be excluded if alternative paths outside the cycle are lighter). Assuming the heaviest edge incident on a vertex cannot be in the MST (it must be included if it is a bridge / leaf incident edge). Assuming an edge with overall global minimum weight must appear in every MST when multiple equal min-weight edges exist (e.g., in an equilateral triangle K3). Confusing shortest-path tree distances with MST path distances (MST minimizes total edge sum, not individual pairwise distances). Overcounting or undercounting MSTs when multiple duplicate-weight edges form internal cycles versus component-connecting bridges.

Minimum Spanning Trees

13 Qs · since 2011 · 23 marks · 1 marks/paperStandard yield

Take topic test

Minimum Spanning Trees (MST) in GATE CS is tested heavily via theoretical properties (Cut and Cycle theorems), counting the number of distinct MSTs using Kruskal's stage-by-stage c… Guide

Type

GATE CSE 2026 Set 1Q49MSQ2 marksMediumLet $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?
GATE CSE 2025 Set 1Q18MCQ1 markEasyLet $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$ . For any two vertices, $u$ and $v$ , let $d_1(u, v)$ and $d_2(u, v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$ , respectively. Which ONE of the options is CORRECT for all…
GATE CSE 2024 Set 2Q51MSQ2 marksMediumLet $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statements is/are TRUE for every such graph $G$ ?
GATE CSE 2024 Set 2Q59NAT2 marksMediumDiagramThe number of distinct minimum-weight spanning trees of the following graph is ________
GATE CSE 2021 Set 1Q17NAT1 markMediumDiagramConsider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is _________.
GATE CSE 2021 Set 2Q1MCQ1 markMediumLet $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$ : There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$ . $S_2$ : If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning tree. Which one of…
GATE CSE 2020Q31MCQ2 marksMediumLet $G = (V,E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighted edge $(u, v) \in V \times V$ is added to $G$ . The worst case time complexity of determining if $T$ is still an MST of the resultant graph is
GATE CSE 2020Q49NAT2 marksEasyConsider a graph $G = (V, E)$ , where $V = \{v_1, v_2, ..., v_{100}\}$ , $E = \{(v_i, v_j)|1 \le i < j \le 100\}$ , and weight of the edge $(v_i, v_j)$ is $|i - j|$ . The weight of minimum spanning tree of $G$ is _______.
GATE CSE 2016 Set 1Q39NAT2 marksMediumLet $G$ be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of $G$ can have is _______.
GATE CSE 2016 Set 1Q40MCQ2 marksMedium $G = (V,E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$ . Which of the following statements about the minimum spanning trees (MSTs) of $G$ is/are TRUE? I. If $e$ is the lightest edge of some cycle in $G$ , then every MST of $G$ includes $e$ …
GATE CSE 2012Q29MCQ2 marksMediumLet $G$ be a weighted graph with edge weights greater than one and $G^{\prime}$ be the graph constructed by squaring the weights of edges in $G$ . Let $T$ and $T^{\prime}$ be the minimum spanning trees of $G$ and $G^{\prime}$ , respectively, with total weights $t$ and $t^{\prime}$ . Which of the following statements is TRUE?
GATE CSE 2011Q54MCQ2 marksMediumDiagramStatement for Linked Answer Questions 54 and 55: An undirected graph $G(V, E)$ contains $n$ ( $n > 2$ ) nodes named $v_1, v_2, \ldots, v_n$ . Two nodes $v_i, v_j$ are connected if and only if $0 < |i - j| \le 2$ . Each edge $(v_i, v_j)$ is assigned a weight $i + j$ . A sample graph with $n = 4$ is shown…
GATE CSE 2011Q55MCQ2 marksMediumThe length of the path from $v_5$ to $v_6$ in the MST of previous question with $n = 10$ is

Topic guide

What does GATE test in Minimum Spanning Trees?

Minimum Spanning Trees (MST) in GATE CS is tested heavily via theoretical properties (Cut and Cycle theorems), counting the number of distinct MSTs using Kruskal's stage-by-stage component logic, and parameterized/algebraic graph constructions. Questions frequently explore fundamental cycle edge swaps, algorithm time complexities for dynamic updates, and the structural relationship between graph shortest paths and tree paths.

Core concepts

Cut Property: minimum weight edge crossing any cut is in an MST
Cycle Property: strictly maximum weight edge in any cycle is not in any MST
Vertex Cut Instance: lightest edge incident on any vertex v must be in an MST (cut \v\ vs V \v\)
Kruskal's Algorithm and independent component counting across equal-weight edge batches
Fundamental cycles and edge exchange property
MST uniqueness under strictly distinct edge weights
Monotonic weight transformations and preservation of MST edge sets
Dynamic MST validation via tree path bottleneck check in (|V|) time

Recurring question patterns

Counting Distinct MSTs
common · NAT · 2 marks · 2024, 2021
A weighted undirected graph with duplicate edge weights is provided (often as a visual diagram). Candidates must determine the exact number of distinct MSTs by analyzing independent component connections at each weight class in Kruskal's algorithm.
Cut and Cycle Properties & Structural True/False
common · MSQ · 2 marks · 2026, 2021, 2016
Evaluating formal claims about whether the lightest or heaviest edge in a cycle, cut, or vertex incidence set is guaranteed to be inside or outside an MST, including uniqueness conditions.
Algebraically Defined Vertex-Index Graphs
occasional · MCQ · 2 marks · 2020, 2011
Graphs where vertices are indexed $v_1, \dots, v_n$ and edge existence/weights are given as functions of indices (e.g., $|i-j| \le 2$ with weight $i+j$ , or complete graph with weight $|i-j|$ ). Questions ask for MST total weight formula or path lengths in the tree.
MST Maintenance & Subgraph Comparisons
occasional · MCQ · 2 marks · 2025, 2020, 2012
Analyzing algorithmic complexity or metric bounds when modifying an existing MST, such as testing if $T$ remains an MST after adding a single edge, monotonic weight transformations ( $w \to w^2$ ), or comparing shortest-path distances $d_G(u,v)$ vs $d_T(u,v)$ .
Spanning Tree Parity and Fundamental Cycles
rare · MSQ · 2 marks · 2024, 2016
Reasoning about properties of all spanning trees in a graph using the fundamental cycle edge-exchange argument $T^{\prime} = (T \cup \{e\}) \setminus \{e^{\prime}\}$ to prove parity or weight bounds.

Formulas GATE uses

MST Tree Size Condition

|E(T)| = |V| - 1

Determining total number of edges required to form a valid spanning tree on $|V|$ vertices.

Fundamental Cycle Weight Exchange

w(T^{\prime}) = w(T) + w(e) - w(e^{\prime}) \quad \text{where } e^{\prime} \in \text{path}_T(u, v)

Analyzing tree transformations when adding non-tree edge $e=(u,v)$ and removing an edge $e^{\prime}$ from the induced cycle.

Monotonic Weight Scaling Expansion

t^2 = \left(\sum_{i=1}^{n-1} w_i\right)^2 = \sum_{i=1}^{n-1} w_i^2 + 2\sum_{i < j} w_i w_j = t^{\prime} + 2\sum_{i < j} w_i w_j

Comparing total tree weight before and after strictly monotonic transformations on edge weights.

Subgraph Distance Inequality

d_G(u, v) \le d_T(u, v)

Comparing the shortest path distance in graph $G$ vs distance in a spanning tree $T \subseteq G$ .

Examiner traps in Minimum Spanning Trees

Assuming the lightest edge in a cycle must be in the MST (it can be excluded if alternative paths outside the cycle are lighter).
Assuming the heaviest edge incident on a vertex cannot be in the MST (it must be included if it is a bridge / leaf incident edge).
Assuming an edge with overall global minimum weight must appear in every MST when multiple equal min-weight edges exist (e.g., in an equilateral triangle K3).
Confusing shortest-path tree distances with MST path distances (MST minimizes total edge sum, not individual pairwise distances).
Overcounting or undercounting MSTs when multiple duplicate-weight edges form internal cycles versus component-connecting bridges.

How questions are asked

NAT: Count the exact number of distinct MSTs in a given weighted graph
NAT: Find the maximum or minimum possible weight of an MST given a set of edge weights
MCQ/MSQ: Identify correct theoretical statements on Cycle and Cut properties
MCQ: Determine asymptotic time complexity for dynamic graph/tree update operations
MCQ: Derive a closed-form formula for MST weight in parameterized graphs

Paper trends

Shift from linked MCQ and formula derivation toward NAT counting questions and multi-correct MSQs verifying nuanced cut/cycle edge properties.
2026, 2024, 2021, 2011
Increased focus on structural reasoning involving tree paths and fundamental cycles (e.g., dynamic edge insertion checking in O(|V|), parity invariance across fundamental cycles).
2025, 2024, 2020

Difficulty notes

Easy questions test direct definitions like $d_G(u,v) \le d_T(u,v)$ or simple path MST calculations on index-weighted graphs. Medium questions require multi-step Kruskal component combinatorics (NAT) or rigorous counterexample evaluation for Cut/Cycle MSQ statements. Hard questions require structural tree invariance proofs (such as parity preservation across all fundamental cycles) or worst-case extremal configuration analysis.

Minimum Spanning Trees

13 Qs · since 2011 · 23 marks · 1 marks/paperStandard yield

Take topic test

Minimum Spanning Trees (MST) in GATE CS is tested heavily via theoretical properties (Cut and Cycle theorems), counting the number of distinct MSTs using Kruskal's stage-by-stage c… Guide

Type

Topic guide

What does GATE test in Minimum Spanning Trees?

Core concepts

Cut Property: minimum weight edge crossing any cut is in an MST
Cycle Property: strictly maximum weight edge in any cycle is not in any MST
Vertex Cut Instance: lightest edge incident on any vertex v must be in an MST (cut \v\ vs V \v\)
Kruskal's Algorithm and independent component counting across equal-weight edge batches
Fundamental cycles and edge exchange property
MST uniqueness under strictly distinct edge weights
Monotonic weight transformations and preservation of MST edge sets
Dynamic MST validation via tree path bottleneck check in (|V|) time

Recurring question patterns

Counting Distinct MSTs
common · NAT · 2 marks · 2024, 2021
A weighted undirected graph with duplicate edge weights is provided (often as a visual diagram). Candidates must determine the exact number of distinct MSTs by analyzing independent component connections at each weight class in Kruskal's algorithm.
Cut and Cycle Properties & Structural True/False
common · MSQ · 2 marks · 2026, 2021, 2016
Evaluating formal claims about whether the lightest or heaviest edge in a cycle, cut, or vertex incidence set is guaranteed to be inside or outside an MST, including uniqueness conditions.
Algebraically Defined Vertex-Index Graphs
occasional · MCQ · 2 marks · 2020, 2011
Graphs where vertices are indexed $v_1, \dots, v_n$ and edge existence/weights are given as functions of indices (e.g., $|i-j| \le 2$ with weight $i+j$ , or complete graph with weight $|i-j|$ ). Questions ask for MST total weight formula or path lengths in the tree.
MST Maintenance & Subgraph Comparisons
occasional · MCQ · 2 marks · 2025, 2020, 2012
Analyzing algorithmic complexity or metric bounds when modifying an existing MST, such as testing if $T$ remains an MST after adding a single edge, monotonic weight transformations ( $w \to w^2$ ), or comparing shortest-path distances $d_G(u,v)$ vs $d_T(u,v)$ .
Spanning Tree Parity and Fundamental Cycles
rare · MSQ · 2 marks · 2024, 2016
Reasoning about properties of all spanning trees in a graph using the fundamental cycle edge-exchange argument $T^{\prime} = (T \cup \{e\}) \setminus \{e^{\prime}\}$ to prove parity or weight bounds.

Formulas GATE uses

MST Tree Size Condition

|E(T)| = |V| - 1

Determining total number of edges required to form a valid spanning tree on $|V|$ vertices.

Fundamental Cycle Weight Exchange

w(T^{\prime}) = w(T) + w(e) - w(e^{\prime}) \quad \text{where } e^{\prime} \in \text{path}_T(u, v)

Analyzing tree transformations when adding non-tree edge $e=(u,v)$ and removing an edge $e^{\prime}$ from the induced cycle.

Monotonic Weight Scaling Expansion

t^2 = \left(\sum_{i=1}^{n-1} w_i\right)^2 = \sum_{i=1}^{n-1} w_i^2 + 2\sum_{i < j} w_i w_j = t^{\prime} + 2\sum_{i < j} w_i w_j

Comparing total tree weight before and after strictly monotonic transformations on edge weights.

Subgraph Distance Inequality

d_G(u, v) \le d_T(u, v)

Comparing the shortest path distance in graph $G$ vs distance in a spanning tree $T \subseteq G$ .

Examiner traps in Minimum Spanning Trees

Assuming the lightest edge in a cycle must be in the MST (it can be excluded if alternative paths outside the cycle are lighter).
Assuming the heaviest edge incident on a vertex cannot be in the MST (it must be included if it is a bridge / leaf incident edge).
Assuming an edge with overall global minimum weight must appear in every MST when multiple equal min-weight edges exist (e.g., in an equilateral triangle K3).
Confusing shortest-path tree distances with MST path distances (MST minimizes total edge sum, not individual pairwise distances).
Overcounting or undercounting MSTs when multiple duplicate-weight edges form internal cycles versus component-connecting bridges.

How questions are asked

NAT: Count the exact number of distinct MSTs in a given weighted graph
NAT: Find the maximum or minimum possible weight of an MST given a set of edge weights
MCQ/MSQ: Identify correct theoretical statements on Cycle and Cut properties
MCQ: Determine asymptotic time complexity for dynamic graph/tree update operations
MCQ: Derive a closed-form formula for MST weight in parameterized graphs

Paper trends

Shift from linked MCQ and formula derivation toward NAT counting questions and multi-correct MSQs verifying nuanced cut/cycle edge properties.
2026, 2024, 2021, 2011
Increased focus on structural reasoning involving tree paths and fundamental cycles (e.g., dynamic edge insertion checking in O(|V|), parity invariance across fundamental cycles).
2025, 2024, 2020