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

Let's analyze the two statements regarding the properties of a Minimum Spanning Tree (MST) in a connected undirected weighted graph \(G\):

1. Statement \(S_1\): There exists a minimum weight edge in \(G\) which is present in every minimum spanning tree of \(G\).
   - This statement is false. In a graph, a minimum weight edge is not necessarily present in every Minimum Spanning Tree (MST) unless it is a part of the cycle where it is the only minimum edge.
   - To counter this, consider a situation where the minimum weight edge might be part of multiple cycles. In such cases, removing the edge might still result in a spanning tree of the same minimum total weight, meaning that edge is not critical to every MST.
2. Statement \(S_2\): If every edge in \(G\) has distinct weight, then \(G\) has a unique minimum spanning tree.
   - This statement is true. If the weights of all edges are distinct, then there cannot be two different MSTs. The reason is that any algorithm like Kruskal's or Prim's will proceed edge by edge in increasing order, and there cannot be ambiguity in choosing edges since no two edges have the same weight.
   - Therefore, having distinct edge weights ensures a unique MST.

Conclusion: Based on the above analysis, the correct option is: \(S_1\) is false and \(S_2\) is true.