13,759 views
36 votes
36 votes

An undirected graph $G$ has $n$ nodes. its adjacency matrix is given by an $n \times 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?

  1. Graph $G$ has no minimum spanning tree (MST)

  2. Graph $G$ has unique MST of cost $n-1$

  3. Graph $G$ has multiple distinct MSTs, each of cost $n-1$

  4. Graph $G$ has multiple spanning trees of different costs

2 Answers

Best answer
42 votes
42 votes
Graph $G$ has multiple distinct MSTs, each of cost  $n-1$

From the given data given graph is a complete graph with all edge weights $1$. A MST will contain $n-1$ edges . Hence weight of MST is $n-1$.

The graph will have multiple MST. In fact all spanning trees of the given graph wll be MSTs also since all edge weights are equal.
edited by
2 votes
2 votes
  1. since its a complete graph, its connected, and there will exist a MST, hence this statement is wrong.
  2. If you gotta have a unique cost of (n-1), your weights must be 1. Ofcourse this might be true, but won’t always be true if every weight is same and its = 1.
  3. Very much true.
  4. Very much false, if there are more than 2 msts existing for a graph, they will never have different costs, but always the same.
Answer:

Related questions