Question

If minimum cost edge of a graph is unique, then that edge will be added to any MST. Choose the correct option.

(a) false

(b) maximum cost edge is added

(c) true

(d) minimum cost edge need not be unique

I got this question in examination.

This question is from Spanning Trees in portion Trees of Discrete Mathematics

Answer 1

Right option is (c) true

To elaborate: If the edge was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight. Thus, if the minimum cost edge e of a graph is unique, then this edge is included in any MST.