Q.From a complete graph by removing maximum_______ edges, we can construct a spanning tree.
Correct answer: e – n + 1
Explanation
A complete graph with n vertices has ( ) − n n 1 = e edges. A spanning tree of a graph with n 2 vertices has n – 1 edges. When remove the edges of the spanning tree from the complete graph, the number of edges left is e – (n – 1). Thus, after removing the edges of a spanning tree, the graph will have e – n + 1.
A complete graph with n vertices has ( ) − n n 1 = e edges. A spanning tree of a graph with n 2 vertices has n – 1 edges. When remove the edges of the spanning tree from the complete graph, the number of edges left is e – (n – 1). Thus, after removing the edges of a spanning tree, the graph will have e – n + 1.