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

The graph is connected and it has N vertices and edges then it is sufficient condition for existence of cycle. Therefore for a cycle we need atleast of 3 vertices and it has 3 different spannig tress.

From this we can say N>3 has atleast of 3 different Spanning Tress possible..

Am i right or wrong Lemme known...sir

@GO Classes

---

A graph with n vertices and n edges:

• A tree with n vertices has exactly n−1 edges.

• Adding one more edge makes it n edges and creates a cycle.

We know a tree + 1 edge always forms a cycle. The smallest possible cycle is a triangle (3 edges). Removing one edge from this cycle at a time gives a spanning tree.

Hence, the minimum number of spanning trees is 3.

Answer: 3

---

Since the question asks for a number \(m\) that is guaranteed to work for every<!--TgQPHd|||[]--> possible simple graph with \(n\) vertices and \(n\) edges, we must look at the worst-case scenario.<!--TgQPHd|||[]-->

The absolute smallest cycle a simple graph can have is a 3-edge cycle (a triangle). By removing any one of those 3 edges, you break the cycle and get a unique spanning tree. That gives you exactly 3 different spanning trees.<!--TgQPHd|||[]-->

If the cycle happened to be larger (like a square with 4 edges), you would get 4 spanning trees. But since we need a minimum guarantee ("at least \(m\)"), 3<!--TgQPHd|||[]--> is the largest integer that safely works for every single case.

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

nice explaination

---

"At least" is the one making difference. For n=4 simple graph we get 4 spanning trees and for n=5 we also get 4 spanning trees. So we're getting minimum 3 spanning trees.

---

The min no. of spanning trees possible will always depend on min len cycle possible. cuz it can form a cycle graph or min cycle of 3 vertices or cycle of any no. of vertices n-k. but in any graph the min len cycle possible is of len 3 so here atleast 3 mst are possible.

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

---

i think here most confusing word is atlest  (kam se kam)  so if we have length of three cycle graph then we can make atlest (kam se kam) 3 graph,   we can make more then 3 spanning tree by take 4 length cycle or 5 length cycle and so on, but here they are asking atleast.

Answer 3

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.

---

I have tagged your ans as useful

Answer 4

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 5

Yeh samajhne ke liye ki kyun answer 3 hai, humein yeh dekhna hoga ki kisi bhi simple connected graph mein jisme n vertices aur n edges hain to usme pakki ek cycle hogi), agar hum cycle se koi bhi edge hata dete hain, toh bhi graph connected rehta hai aur ek spanning tree banta hai. Sabse chhoti cycle jo ban sakti hai woh hai ek triangle , jisme 3 vertices aur 3 edges hote hain. Is triangle se agar aap koi bhi edge hata dete hain to exactly 3 alag spanning trees ban sakte hain. Aur badi koi bhi cycle isse zyada spanning trees ki sambhavana toh rakhti hi hai, lekin zaroori nahi ki wo unique configurations mein ho. Isliye, 3 wo minimum guaranteed number hai jo kisi bhi aise graph configuration mein spanning trees ke liye ho sakta hai, kyun ki koi bhi graph configuration 3 se kam spanning trees produce nahi kar sakta jab tak ki yeh conditions poori hoti hain.

Answer 6

Since its mentioned that its simple graph, hence vertices=2 and edges=2 are not allowed.

So for least value consider Vertices=3 and Edges=3. There will be minimum 3 spanning tree.

For vertices=4 and edges=4, there will be minimum 4 spanning tree.….. and so on.

The minimum spanning trees for simple graph is 3. Option C