Question

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?

• A. Both \(S_1\) and \(S_2\) are true.
• B. \(S_1\) is true and \(S_2\) is false.
• C. \(S_1\) is false and \(S_2\) is true.
• D. Both \(S_1\) and \(S_2\) are false.

Hint:

Distinct edge weights in a graph always ensure a unique minimum spanning tree, but minimum-weight edges need not appear in all MSTs.

Answer 1

The Correct Option is C

Step 1: Analysis of Statement \(S_1\).
A minimum weight edge in a graph is not necessarily present in every minimum spanning tree. If there are multiple edges with the same minimum weight forming cycles, different MSTs can exclude different minimum edges. Hence, the claim that a minimum weight edge must appear in every MST is incorrect. Therefore, \(S_1\) is false.

Step 2: Analysis of Statement \(S_2\).
If all edge weights in a graph are distinct, then no two spanning trees can have the same total weight. This guarantees the uniqueness of the minimum spanning tree. This is a well-known property of MSTs. Hence, \(S_2\) is true.

Step 3: Conclusion.
Since \(S_1\) is false and \(S_2\) is true, the correct option is (C).