Question

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?

• A. If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight
• B. Every minimum spanning tree has an edge of weight w
• C. e is present in every minimum spanning tree
• D. There is a minimum spanning tree containing e

Answer 1

The correct option is C e is present in every minimum spanning tree

W be the minimum weight among all edge weigts in an undirected connected graph.

e is the specific edge of weight w. It may be possible that another edge in the graph having weight w which had been added to minimum spanning tree and when we add e to minimum spanning tree it form a simple circuit.

So we can't include e in every minimum spanning tree.