Question

Let $G$ be an undirected connected graph with distinct edge weights.

Let $e_{\text{max}}$ be the edge with maximum weight and $e_{\text{min}}$ be the edge with minimum weight.

Which of the following statements is false?

• A. No minimum spanning tree contains $e_{\text{max}}$
• B. $G$ has a unique minimum spanning tree
• C. If $e_{\text{max}}$ is in a minimum spanning tree, then its removal must disconnect $G$
• D. Every minimum spanning tree of $G$ must contain $e_{\text{min}}$

Answer 1

The correct option is C If $e_{\text{max}}$ is in a minimum spanning tree, then its removal must disconnect $G$

All edges are distinct weights.
Removal of $e_{\text{max}}$ may not disconnect $G$, because other edges may cover the vertices incident with $e_{\text{max}}$