Let G be an undirected connected graph with distinct edge weights. Let e_max…
2000
Let G be an undirected connected graph with distinct edge weights. Let e_max be the edge with maximum weight and e_min be 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 removing e_max must disconnect G
- C.
No minimum spanning tree contains e_max
- D.
G has a unique minimum spanning tree
Attempted by 6 students.
Show answer & explanation
Correct answer: C
Since all edge weights are distinct, the MST of G is unique, so statement D is true.
The globally minimum-weight edge e_min must be included in the MST by the cut property, so statement A is true.
If e_max belongs to an MST, then it cannot lie on any cycle in G. If it did, it would be the heaviest edge on that cycle and the cycle property would exclude it from every MST. Hence e_max must be a bridge, so removing it disconnects G. Thus statement B is true.
Statement C says that no MST contains e_max. This is false: if G itself is a tree, every edge, including e_max, belongs to the only spanning tree/MST. More generally, a maximum-weight bridge must be included. Therefore, C is the false statement.