GATE CS 2021 Set 2 Q.11 (CS Q.1): Minimum Spanning Trees

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?

Both $S_1$ and $S_2$ are true.

$S_1$ is true and $S_2$ is false.

$S_1$ is false and $S_2$ is true.

Both $S_1$ and $S_2$ are false.

Official answer and solution

Official answer: C
From: Official GATE 2021 answer key

Solution

Evaluate standard minimum spanning tree properties regarding non-unique edge weights and distinct edge weights.

Consider statement $S_1$ : 'There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$ '.
Consider a counterexample: a cycle graph $C_3$ (triangle) with all three edge weights equal to 1. The minimum weight in the graph is 1. Any MST consists of any 2 edges. For each individual edge, there exists an MST that excludes it. Thus, no single minimum-weight edge is present in every MST. Therefore, $S_1$ is false.

Consider statement $S_2$ : 'If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning tree'.
By the cut property of minimum spanning trees, for every cut, the unique minimum-weight crossing edge must belong to the MST. Because edge weights are distinct, every cut has a unique minimum crossing edge. By Kruskal's or Prim's algorithm, deterministic choices produce a single unique tree. Therefore, $S_2$ is true.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 11 of 65, printed as CS Q.1
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source