Let G be a connected undirected weighted graph. Consider the following two…
2021
Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: 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 S1 and S2 are true
- B.
S1 is true and S2 is false
- C.
S1 is false and S2 is true
- D.
Both S1 and S2 are false
Attempted by 313 students.
Show answer & explanation
Correct answer: C
Answer: S1 is false, S2 is true
Why S1 is false (counterexample):
Consider a triangle with vertices A, B, C where each of the three edges has the same minimum weight (for example, weight 1). Any spanning tree must pick exactly two of these edges. For any particular minimum-weight edge you choose, there exists an MST that omits that edge (pick the other two). Therefore there is no minimum-weight edge that is present in every MST.
Why S2 is true (proof by exchange argument):
Assume all edge weights are distinct and, for contradiction, that there are two different minimum spanning trees T1 and T2.
Let e be the smallest-weight edge (by weight) that belongs to one tree but not the other; without loss of generality assume e is in T1 but not in T2.
Adding e to T2 creates a cycle. That cycle must contain some edge f that is in T2 but not in T1. Because e was chosen as the smallest differing edge, weight(e) < weight(f).
Replacing f by e in T2 gives a spanning tree with strictly smaller total weight than T2, contradicting the minimality of T2.
Hence no two different MSTs can exist when all edge weights are distinct, so the MST is unique.
Summary: S1 is false (counterexample: triangle with equal minimum edges). S2 is true (distinct weights force a unique MST by the exchange argument).
A video solution is available for this question — log in and enroll to watch it.