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

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

---

We assume this 

---

broo all undignoal elements are 1

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

@Abhrajyoti00 why should we consider it same?

 

---

@nayab.rasool 

When you will draw the graph as an adjacency matrix it means that wherever is 1 in the matrix an edge is present, there is no need to consider if edge weights are same or different, the question focuses on the fundamentals of MST and you need to consider the cases that involve some good number of vertices.

In the above comments somebody proves none option is correct by taking n count as 2.

I mean why will you even find MST or a spanning tree for a graph with 2 vertices. 

---

I have a doubt, 
its no where mentioned whether the vertices are labelled
So some spanning trees will be isomorphic
For example,
consider K3( unlaballed), There are 3 spanning trees but all are isomorphic
So does distinct spanning trees hold true?
 

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

---

But in option D they talk about Spanning tree  not Minimum Spanning tree, so n^n-2 spanning trees possible of different length but and multiple MST possible of same cost
 

Answer 3

Correct option is C, since there can be multiple spanning trees for given graph, but cost will be same

Answer 4

 

---

Minimum Spanning Tree (MST) – Explanation Using Triangle (n = 3)

Given:

An undirected graph ( G ) with:

• ( n ) nodes

• Adjacency matrix:

  • Diagonal elements = 0 (no self-loops)

  • Non-diagonal elements = 1 (all nodes connected)

 This represents a complete graph where every pair of nodes is connected with weight = 1.

---

Example: Triangle Graph (n = 3)

Figure:

     A
    / \
   /   \
  B-----C

---

Adjacency Matrix:

     A  B  C
A → [0  1  1]
B → [1  0  1]
C → [1  1  0]

---

MST Concept:

• A Minimum Spanning Tree connects all nodes

• Has no cycles

• Contains exactly ( n - 1 ) edges

For ( n = 3 ):
👉 MST must have 2 edges

---

All Possible MSTs:

MST 1:

Edges: A–B, B–C
Cost = 1 + 1 = 2

MST 2:

Edges: A–B, A–C
Cost = 2

MST 3:

Edges: A–C, B–C
Cost = 2

---

Observations:

• Multiple MSTs exist

• Each MST has same cost = 2

• ( 2 = n - 1 )

---

Final Answer:

Graph G has multiple distinct MSTs, each of cost ( (n - 1) )

---

Key Insight (Exam Point):

• Complete graph + equal edge weights
  Always gives:

• Multiple MSTs

• Each with cost ( n - 1 )

---

 

Answer 5

Simplest Question, Let's read the Explanation in detail 

Comments

for n=2 we get only one MST possible and there is a chance we think B is correct but yeah ig i was dumb lol , we need to check for n=3 theen make conclusions!