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.

GATE CSE Minimum Spanning Trees PYQs

Standard yield12.4% of Algorithms

Minimum Spanning Trees (MST) in GATE CS is tested heavily via theoretical properties (Cut and Cycle theorems), counting the number of distinct MSTs using Kruska… Read the guide

Take topic test

Questions: 13
Asked: since 2011
Total marks: 23
Marks / paper: 1

13 GATE CSE Minimum Spanning Trees PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Minimum Spanning Trees

Concepts, patterns, formulas and traps distilled from past papers.

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
CommonNAT2 marks2024, 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
CommonMSQ2 marks2026, 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
OccasionalMCQ2 marks2020, 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
OccasionalMCQ2 marks2025, 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
RareMSQ2 marks2024, 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.