What are common examiner traps in Graph Traversals, MSTs and Shortest Paths?

Assuming shortest paths remain unchanged when adding a constant c to all edges (paths with fewer edges gain an advantage over paths with many edges). Assuming shortest path is unique when all edge weights are distinct (different combinations of distinct weights can sum to identical path lengths). Failing to enforce 'strictly less than' (x < min) when a question asks for inclusion in EVERY MST instead of 'SOME MST'. Forgetting that all edge weights must remain distinct integers when finding minimum total weight bounds. Multiplying |E| instead of (|V| - 1) when computing the total weight increase of an MST after adding a constant to all edges.

GATE CSE Graph Traversals, MSTs and Shortest Paths PYQs

Q: What does GATE test in Graph Traversals, MSTs and Shortest Paths?

GATE questions on this topic heavily emphasize structural properties and theoretical invariants of Minimum Spanning Trees (MSTs) rather than raw algorithmic execution traces. Recurring themes include the Cut Property, the Cycle Property, distinct vs. non-distinct edge weights, and the invariance of MSTs under linear weight transformations compared to Shortest Paths. A typical problem presents either a small concrete graph (often with an unknown parameter or repeated weights) or a set of theoretical assertions evaluated across graph classes.

Standard yield7% of Algorithms

GATE questions on this topic heavily emphasize structural properties and theoretical invariants of Minimum Spanning Trees (MSTs) rather than raw algorithmic exe… Read the guide

Take topic test

Questions: 7
Asked: since 2014
Total marks: 13
Marks / paper: 0.5

7 GATE CSE Graph Traversals, MSTs and Shortest Paths PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Graph Traversals, MSTs and Shortest Paths

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

GATE questions on this topic heavily emphasize structural properties and theoretical invariants of Minimum Spanning Trees (MSTs) rather than raw algorithmic execution traces. Recurring themes include the Cut Property, the Cycle Property, distinct vs. non-distinct edge weights, and the invariance of MSTs under linear weight transformations compared to Shortest Paths. A typical problem presents either a small concrete graph (often with an unknown parameter or repeated weights) or a set of theoretical assertions evaluated across graph classes.

Core concepts

Cut Property and Cycle Property of MSTs
Uniqueness of MST when all edge weights are distinct
Non-uniqueness of shortest paths even when edge weights are distinct
Effect of adding a positive constant c to all edge weights on MST (invariant) vs. Shortest Paths (can change)
Kruskal's algorithm edge selection order (lightest edge e1 always present; e2 always present in simple graphs; at least one of e3, e4 present)
Counting combinations of equivalent-weight edges to find total number of distinct MSTs

Recurring question patterns

Parameter Constrained MST Inclusion
OccasionalNAT2 marks2025
A weighted graph is given with one edge weight specified as a variable $x$ . Students must find the maximum or minimum integer value of $x$ such that the edge is included in every (or some) MST using cut/cycle properties.
Counting Distinct MSTs
OccasionalNAT2 marks2014
A weighted graph with non-distinct edge weights is provided. Students determine the total number of distinct spanning trees that achieve the minimum weight by evaluating independent choices in Kruskal's algorithm.
MST Reconstruction and Cycle Property Bounds
OccasionalNAT2 marks2015
Given a subset of edges forming an MST with distinct weights, students determine the minimum (or maximum) possible total sum of all edge weights in the graph by applying $w(u, v) > \max_{e \in \text{path}(u, v)} w(e)$ for all non-tree edges.
MST vs. Shortest Path Invariant Properties
Commonmixed2 marks2022, 2017, 2016, 2015
Theoretical assertions comparing how graph transformations (e.g., adding a constant $c$ to all edge weights) or edge weight constraints (e.g., distinct weights) affect MST uniqueness and structure versus shortest paths.

Formulas GATE uses

Spanning Tree Edge Count

|E_{\text{MST}}| = |V| - 1

Used to compute the new MST weight after adding a constant scalar $c$ to all edge weights: $W_{\text{new}} = W_{\text{old}} + (|V| - 1) \cdot c$ .

Cycle Property of MST

w(u, v) > \max_{e \in \text{path}_{T}(u, v)} w(e)

Determines the lower bound on the weight of a non-tree edge $(u, v)$ when edge weights are distinct and $T$ is the MST.

Cut Property for Strict MST Inclusion

w(u, v) < \min_{e \in (S, V \setminus S) \setminus \{(u, v)\}} w(e)

Ensures an edge $(u, v)$ crossing a non-trivial cut $(S, V \setminus S)$ is strictly required in EVERY MST.

Examiner traps in Graph Traversals, MSTs and Shortest Paths

Assuming shortest paths remain unchanged when adding a constant c to all edges (paths with fewer edges gain an advantage over paths with many edges).
Assuming shortest path is unique when all edge weights are distinct (different combinations of distinct weights can sum to identical path lengths).
Failing to enforce 'strictly less than' (x < min) when a question asks for inclusion in EVERY MST instead of 'SOME MST'.
Forgetting that all edge weights must remain distinct integers when finding minimum total weight bounds.
Multiplying |E| instead of (|V| - 1) when computing the total weight increase of an MST after adding a constant to all edges.

How questions are asked

Compute total number of distinct MSTs from a visual graph
Calculate updated MST weight after edge weight scalar shift
Find minimum possible sum of all graph edges given an MST
Find maximum/minimum parameter value x for guaranteed edge inclusion
Evaluate truth value of multi-statement theoretical claims on MST and shortest paths

Paper trends

Shift from simple uniform weight modification NATs and conceptual MCQs toward multi-concept MSQs and optimization/parameter-bounding NATs.
2025, 2022, 2017, 2016, 2015, 2014
Increased focus on testing fundamental MST properties (Cut Property, Cycle Property, Kruskal step logic) via edge rank statements and parameter bounds rather than standard execution traces.
2025, 2022

Difficulty notes

Easy: Direct calculation of MST weight change under a uniform shift $(|V|-1)c$ , or standard 1-statement properties. Medium: Applying cycle property to deduce missing non-tree edge weights, evaluating Cut/Cycle properties in MSQs, finding parameter bounds for MST inclusion, or counting distinct MSTs across multiple disjoint edge choices. Hard: Combinations of multiple parameter inequalities or complex topological cuts with overlapping cycles.