GATE CSE 2005 | Question: 6

Question

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?

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

• B. Graph $G$ has 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

Comments

here given n×n square matrix whose

(i) diagonal elements are 0’s and

(ii) non-diagonal elements are 1’s.

it means on same node there is no edge, but from one node to all other nodes there is an edge. but nothing is mentioned regarding weight so how we can say Graph G has multiple distinct MSTs.

---

I found a counter example for option C.

If the number of vertices are 2 then number of unique spanning trees will be only 1. 

So option C becomes wrong. In fact no option is correct.

 

---

Number of vertices can’t be 2 because it is a n*n matrix (e.g 1*1, 2*2,4*4…….n*n)

Answer 1

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.

Comments

No where it is mentioned that each edge weight is 1 here that information is for adjacency matrix,  here 1 denotes that edge is present and 0 denotes edge is not present so your explanation requires some correction please read question carefully.

---

Shivam Kaushik

same doubt!

---

@Shivam Kaushik @Pranavpurkar 

Even if we don’t consider the edge weights to be $1$, we must consider all of the edges to be of same weights (say $w$) because edge weights/cost matrix is not explicitly mentioned.

Answer 2

• A. since its a complete graph, its connected, and there will exist a MST, hence this statement is wrong.
• B. 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.
• C. Very much true.
• D. Very much false, if there are more than 2 msts existing for a graph, they will never have different costs, but always the same.

Comments

I was also thinking $D$ true but point which clicked in my mind
If we even also get different MSTs there may be some MSTs which are different but they may have also same costs. So, in this case $D$ will be never true.

---

Also this

In fact all spanning trees of the given graph wll be MSTs also since all edge weights are equal.

---

Yes @amitarp818