GATE IT 2007 | Question: 25

Question

What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ?

• A. $1$
• B. $2$
• C. $3$
• D. $n$

Comments

I question we are discussing about minimum number, any number more than 3 is poosible, but try to think a way in which as per above conditions we get different spanning trees less than 3

---

hey everyone follow this simple approach,think like this

for every value of n we can  have number of graphs,ok different-different kind we say, for ex n=3 only one graph K3 we will have,for n=4 ,2 diff kind of graph we have i.e. cycle of 4 and a K3 with one edge connected via bridge to one vertex.

like that we can draw a no of diff-diff kind of graphs,but notice one thing which is imp here

in worst case,we will always have kind of graph with k3,along with single single edges -edges as bridge, and that k3 will will always result in atleast 3 diff spanning trees,

conclusion- no matter what kind of graph you have drawn,that k3 will always be there in one graph and will give atleast 3 diff spanning trees.therefor answer is 3.

any corrections,suggestions are welcomed.

---

what if there’s distinct weighted graph?? then max m will be 1 only right??

Answer 1

OPTION (C) is Correct, reason is as follows:

A graph is connected and has '$n$' vertices and edges means, exactly one cycle is there.

Now we can make a different spanning tree by removing one edge from the cycle, one at a time.

Minimum cycle length can be $3$, So, there must be at least $3$ spanning trees in any such graph. 

 

Consider the above graph. Here $n = 4$ and three spanning trees possible at max (removing edges of cycle one at a time, alternatively).

So, any such Graph with minimum cycle length '$3$' will have at least $3$ spanning trees.

Comments

@Prabhjeet6 , 

see this graph and please note that there are only 3 min span trees possible 

---

I think they didn't need to write simple graph.. Its make question not clear. Because simple connected graph don't have cycle or parallel edges

---

@NILESH PINGALE Simple connected graph can have a cycle.

Answer 2

C option.

In a connected graph with N vertices and N edges, there will be only one cycle. So vertices not in this cycle will always be included in the Spanning Tree of this Graph.

Now lets assume that the cycle contains ' X ' edges. To draw spanning Tree of this graph we have to include ' X-1 ' edges from this cycle. In order to do that we need to know how many of the edges in this cycle are cut edges that is because cut edges are always present in the Spanning Tree as there is no other option to cover the vertex which is connected by cut edge.

If you draw the graph you will find that this cycle we will have ' X-3 ' cut edges, so we have to include them. From the remaining 3 edges we have to select 2 edges in ³C₂ ways as we have to select only X-1 edges from this cycle. So every Spanning tree of the graph with N vertices and N edges will have atleast 3 Spanning Tree and atmost N Spanning Trees in case graph is Cyclic.

Comments

Very nice explanation

Answer 3

ans :D

starting from 3 vertices only we can do 3 edges so atleast 3 spanning trees

Comments

Assume the graph to be a circuit of n vertex(i.e., a circuit of n edges)
we can form a minimum spanning tree my removing each of the n edges from the circuit.

so there can be n different spanning trees in a simple connected graph of n edges and n vertex

Answer 4

For confusion on option D as answer.

The question starts from number of nodes = 3, because with 2 nodes there will be only one edge,

which violates the question condition.

For any cycle like figure the answer N seems legit because every time we can remove one edge,

and get one spanning tree, we keep doing this and finally we will have n spanning trees so m=n.

 

But there are counter case to it.

ABCDE is a graph with 5 vertices and 5 edges but we cannot achieve 5 spanning trees.

we can only go upto 4, so is 4 the answer no we can extend this logic to any no of nodes, but

this problem won't go away. But however for No of nodes >= 3 the value of m as 3 always satisfies.

Hence 3 is the ANSWER.

Comments

Bro, You explained it well, I have this doubt, for three nodes, we will get one cycle right if the graph is unlabelled, and three if they are labelled, since nothing is mentioned in the question, the answer can be either one or three too, right.

---

Sir, here we can have 4 MST of 5 vertices graph
please correct me if I'm wrong

 

---

yes it is possible, however they have asked the maximum number among 1,2,3 hence 1 ans 2 cannot be considered. That’s why 3.