Let G be an undirected connected graph with distinct edge weight. Let e_max be…
20002017
Let G be an undirected connected graph with distinct edge weight. Let e_max be the edge with maximum weight and e_min the edge with minimum weight. Which of the following statements is false?
- A.
Every minimum spanning tree of G must contain e_min
- B.
If e_max is in a minimum spanning tree, then its removal must disconnect G
- C.
No minimum spanning tree contains e_max
- D.
G has a unique minimum spanning tree
Attempted by 48 students.
Show answer & explanation
Correct answer: C
In a graph with distinct edge weights, the Minimum Spanning Tree (MST) is unique. By the cut property, the minimum weight edge e_min crossing any cut must be in the MST.
Thus, statement A is true because e_min is always included. However, the maximum weight edge e_max is included if it acts as a bridge.
Therefore, statement C claiming no MST contains e_max is false. Option C is the correct choice for this question.
A video solution is available for this question — log in and enroll to watch it.