Question

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. G has a unique minimum spanning tree
• B. No minimum spanning tree contains $e_{max}$
• C. If $e_{max}$ is in a minimum spanning tree, then its removal must disconnect G
• D. Every minimum spanning tree of G must contain $e_{min}$

Answer 1

The correct option is B No minimum spanning tree contains $e_{max}$

(a) All the edge weights are distinct, so every minimum spanning tree of G must contain $e_{min}$ (kruskal's algorithm will pick $e_{min}$ first)

(b) If $e_{max}$ is in a minimum spanning tree, then surely its removal must disconnect G (i.e. $e_{max}$ must be a cut edge).

(c) A minimum spanning tree can contain $e_{max}$ if its removal disconnect G (i.e. it s a cut edge). So this option is false.

For example, in the graph given below, the edge cd is a maximum weight edge but still is present in the minimum spanning tree.

(d) Since all edge weights are distinct G has a unique minimum spanning tree.