Algorithms · Graph Traversals, MSTs and Shortest Paths
Official IIT answer key · IISc Bangalore · Audited Aug 2026
GATE CSE 2016 Set 1 Q14 · MCQ · 1 mark
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 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
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.
