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.

Graph Traversals, MSTs and Shortest Paths

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.

7 Qs · since 2014 · 13 marks · 0.5 marks/paperStandard yield

Take topic test

GATE questions on this topic heavily emphasize structural properties and theoretical invariants of Minimum Spanning Trees (MSTs) rather than raw algorithmic execution traces. Recur… Guide

Type

GATE CSE 2025 Set 1Q64NAT2 marksMediumDiagramThe maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ________ . (answer in integer)
GATE CSE 2022Q49MSQ2 marksMediumConsider a simple undirected weighted graph $G$ , all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $G$ is/are TRUE?
GATE CSE 2017 Set 1Q26MCQ2 marksEasyLet $G = (V, E)$ be *any* connected undirected edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: (I) Minimum Spanning Tree of $G$ is always unique. (II) Shortest path between any two vertices of $G$ is always unique. Which of the above…
GATE CSE 2016 Set 1Q14MCQ1 markMediumLet $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of $G$ does not change Q: Shortest path between any pair of vertices does not change
GATE CSE 2015 Set 1Q43NAT2 marksMediumDiagramThe graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$ . The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of…
GATE CSE 2015 Set 3Q40NAT2 marksEasyLet $G$ be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of $G$ is 500. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes _______.
GATE CSE 2014 Set 2Q52NAT2 marksMediumDiagramThe number of distinct minimum spanning trees for the weighted graph below is $\underline{\hspace{1cm}}$

Topic guide

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.

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
occasional · NAT · 2 marks · 2025
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
occasional · NAT · 2 marks · 2014
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
occasional · NAT · 2 marks · 2015
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
common · mixed · 2 marks · 2022, 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.