Let G be an undirected connected graph with distinct edge weight. Let Emax be…
2017
Let G be an undirected connected graph with distinct edge weight. Let Emax be the edge with maximum weight and Emin the edge with minimum weight. Which of the following statements is false ?
- A.
Every minimum spanning tree of G must contain Emin.
- B.
If Emax is in minimum spanning tree, then its removal must disconnect G.
- C.
No minimum spanning tree contains Emax.
- D.
G has a unique minimum spanning tree.
Attempted by 241 students.
Show answer & explanation
Correct answer: C
Answer: The statement "No minimum spanning tree contains E_max (the maximum-weight edge)" is false.
Distinct weights imply a unique minimum spanning tree.
The minimum-weight edge of the whole graph must belong to every minimum spanning tree: as the global minimum it is the lightest edge across the cut separating its endpoints, so by the cut property (with no ties) it is included in every MST.
If the maximum-weight edge appears in a minimum spanning tree, then removing it disconnects the original graph: if there were any other edge connecting the two resulting components, that connector would have weight less than the maximum and the MST would use that lighter edge instead, contradicting inclusion of the maximum. Therefore such a maximum edge in an MST must be a bridge.
Thus the statement claiming that no MST contains the maximum-weight edge is false, because the maximum-weight edge can be a bridge (the only edge joining two parts). In that case every spanning tree — and hence every MST — must include that maximum-weight edge. A simple example is two connected subgraphs joined by a single edge that happens to have the largest weight: any spanning tree must include that edge.