An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-diagonal elements are 1‘s. which one of the following is TRUE?
(A)
Graph G has no minimum spanning tree (MST)
(B)
Graph G has a unique MST of cost n-1
(C)
Graph G has multiple distinct MSTs, each of cost n-1
(D)
Graph G has multiple spanning trees of different costs
Answer: (C)
Explanation:
(A) Graph G has no minimum spanning tree (MST): This statement is not true. Every connected graph has at least one minimum spanning tree. Since the graph is complete, it is connected, and thus it must have a minimum spanning tree.
(B) Graph G has a unique MST of cost n-1: This statement is not true either. In a complete graph with n nodes, the total number of edges is given by n(n-1)/2. In this case, every edge has a weight of 1. Therefore, any spanning tree of the graph will have a total weight of n-1, but there can be multiple spanning trees with the same cost.
(C) Graph G has multiple distinct MSTs, each of cost n-1: This statement is true. In a complete graph, any spanning tree will have a total weight of n-1, as explained in option (B). Since the graph has n-1 edges, removing any edge will result in a different spanning tree with the same cost. Thus, there are multiple distinct MSTs, each with a cost of n-1.
(D) Graph G has multiple spanning trees of different costs: This statement is not true. Since all edges in the graph have a weight of 1, all spanning trees will have the same cost of n-1. There will not be multiple spanning trees with different costs.
Hence, the correct answer is (C)
Quiz of this Question
Please comment below if you find anything wrong in the above post