GATE 2021 CS (CS2) – Question 11

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

G is connected, undirected and weighted. S1: Some minimum-weight edge of G is present in every MST. S2: If all edge weights are distinct, G has a unique MST. Which are true?

Both
S1 true,S2 false
S1 false,S2 true
Neither

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) S1 false,S2 true

Explanation

S1 fails for a triangle with all equal weights: each edge is minimum, but each can be omitted by some MST. S2 is the distinct-weight uniqueness theorem, following from the cut/exchange property. Thus S1 is false and S2 true, C.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

GATE 2021 CS (CS2) Q56 – For the directed graph shown, which statements hold?
GATE 2021 CS (CS2) Q65 – In the DAG shown with source s, a path’s quality is the product of its edge weights. A…
GATE 2026 CS (CS1) Q41 – Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a…
GATE 2026 CS (CS1) Q49 – Let G(V, E) be a simple, undirected, edge-weighted graph with unique edge weights. Which…
GATE 2026 CS (CS1) Q50 – Consider the standard depth-first search (DFS) algorithm which takes a directed acyclic…
GATE 2026 CS (CS2) Q37 – Let G be a weighted directed acyclic graph with m edges and n vertices. Given G and a…

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →