Question

Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?

(a) Every minimum spanning tree of G must contain CD

(b) If AB is in a minimum spanning tree, then its removal must disconnect G

(c) No minimum spanning tree contains AB

(d) G has a unique minimum spanning tree

I have been asked this question in an international level competition.

Question is taken from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Right option is (c) No minimum spanning tree contains AB

Easiest explanation - Every MST will contain CD as it is smallest edge. So, Every minimum spanning tree of G must contain CD is true. And G has a unique minimum spanning tree is also true because the graph has edges with distinct weights. So, no minimum spanning tree contains AB is false.