GATE CSE 2021 Set 2 Q11: Minimum weight edge in every MST; distinct weights give unique MST

Let $G$ be a connected undirected weighted graph. Consider the following two statements.

$S_1$ : There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$ .

$S_2$ : If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning tree.

Which one of the following options is correct?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: C (official GATE 2021 final answer key)

Concept used: With ties, different MSTs can avoid any particular minimum-weight edge; with distinct weights the MST is unique.

First step: Test $S_1$ on a triangle whose three edges all have the same weight: which edge is in every spanning tree?

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key