GATE2005-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

how we can say that graph will have distinct spanning trees..

in the qsn only adjacency matrix is gven, the cost matrix is needed to decide whether it will have unique spaaning trees or multiple sppanning trees...what if all the edges in that complete graph is distinct, then it will have only unique spanning tree..

---

actually here , cost matrix should be same as adjacency matrix otherwise one can not decide

---

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.

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

Number of spanning trees in complete graph = $n^{(n-2)} \text{ }$ (Cayley's formula)

---

reference or cayley formula plx

---

@akansh check this link

https://en.wikipedia.org/wiki/Cayley%27s_formula

---

Cayley formula is applicable for graph which is

1)complete graph

2)labeled vertices

3)unweighted graph/or all edge weights are same.

---

@reena is right.

---

yes c is correct

---

undirected too right?

---

you dont have any info about weight matrix.. so option d should be there

---

@ashwani we can form the weight matrix using the given condition

"n×n square matrix whose (i) diagonal elements are 0’s and (ii) non-diagonal elements are 1’s."

---

@lakshaysaini there is no info about weight of edges...so option D should be right.

---

@sushmita

@reena_kandari

unweighted graph/or all edge weights are same.

To apply cayley formula this is not necessary

in Kn , cayley formula gives No of SPANNING TREES not min spanning trees..IF all weights are same/unweighted then all spanning trees are MSTs

---

If the nodes are not labelled, will there be distinct MSTs of cost $n - 1$? Or just the one MST?