Question

Which of the following is false?

(a) The spanning trees do not have any cycles

(b) MST have n – 1 edges if the graph has n edges

(c) Edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph

(d) Removing one edge from the spanning tree will not make the graph disconnected

The question was posed to me in exam.

My question is based upon Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Correct answer is (d) Removing one edge from the spanning tree will not make the graph disconnected

The best explanation: Every spanning tree has n – 1 edges if the graph has n edges and has no cycles. The MST follows the cut property, Edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph.