The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 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

asked in Algorithms by Veteran (59.6k points) | 1.4k views
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.

1 Answer

+21 votes
Best answer
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.
answered by Boss (11.5k points)
edited by
Number of spanning trees in complete graph = $n^{(n-2)} \text{ }$ (Cayley's formula)
reference or cayley formula plx
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,770 questions
47,478 answers
62,241 users