Question

An undirected graph $G$ has $n$ nodes. lts adjacency matrix is given by $n\times n$ square matrix whose

1. diagonal elements are 0's, and
2. non-diagonal elements are 1's.

Which one of the following is TRUE?

• A. Graph $G$ has multiple distinct MST's each of cost $n-1$
• B. Graph $G$ has a unique MST Of cost $n-1$
• C. Graph $G$ has no minimum spanning tree MST
• D. Graph $G$ has multiple spanning trees of different costs

Answer 1

The correct option is A Graph $G$ has multiple distinct MST's each of cost $n-1$

Undirected graph $G$ contains $n$ nodes.



In undirected graph G the diagonal elements are 0 means there is no self loop of any vertex. When each vertex in $G$ is connected through $n$ vertices in the graph $G$ so $G$ is a complete graph.

In a complete graph apply the Cayley's theorem for the total number of minimum spanning tree in a complete graph $G$ with $n$ vertices is $n^2.$

So $G$ has multiple distinct MST's. The cost of its spanning tree is sum of all edges.

If $G$ contains vertices then we will stop the algorithm after adding the $n-1$ edges.

So each spanning tree have a cost $n-1$