Algorithms · Graph Traversals, MSTs and Shortest Paths
Official IIT answer key · IIT Roorkee · Audited Aug 2026
GATE CSE 2017 Set 1 Q26 · MCQ · 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 = (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 statements is/are necessarily true?
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.
