Loading previous year questions
Algorithms · Graph Traversals, MSTs and Shortest Paths
Official IIT answer key · IIT Kanpur · Audited Aug 2026
GATE CSE 2015 Set 3 Q40 · NAT · 2 marks
Key concept
No account needed
Sit 5 related Graph Traversals, MSTs and Shortest PathsPYQs as a guest. We'll score the set and show which traps cost marks — sign in only if you want to save the run.
Topic notes
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.
Full Graph Traversals, MSTs and Shortest Paths guide →All 7 questions on Graph Traversals, MSTs and Shortest Paths →
Let 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 …
Topic-wise GATE CS PYQs with verified steps
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.