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

Here in the ans it is said minimum cycle length is 3 as mentioned in the question if we assume the maximum cycle length then it would be n so on that case ans will be n?

---

No question is atleast m spanning tree. i.e. min spanning tree is 3 and maximum is n

---

Yes @srestha you are correct, we can take e.g cycle graph.

---

I am having difficulties to understand the solution. The graph has two nodes and one cycle. It has two spanning tree. So why we are considering  min=3 spanning tree. In question N is not bound to any number but to make the spanning tree we have to take n>1.

---

You cannot have multiple edges in simple graphh

---

Why haven't we considered the fact that graph may be unlabelled then in that case some of the spanning trees will become isomorph of each other and thus number of spanning tree will get reduced.

---

Thank you @Arjun sir  for reply. I had wrong defination of simple connected graph in my mind.  I checked it again and get clarified. Thank you

---

Where is the multiple edge in given answer?

---

Hi,

I feel the answer should be n.Please let me know the flaw of my logic.

A graph as below

a-b

|   |

c-d

will have 4 spanning trees,

---

@Prabhjeet6 try the same logic for a triangle (3 vertices , 3 edges) n=3

---

1)Here labaled or unlabaled vertex may effect the answer?
2) By default we assume vertex are labaled?

---

Yes in spanning trees we assume vertices are labeled..

---

Is it so? Where is the source? @Verma Ashish

---

@commenter commenter

If not then answer for this question is 2 only which is not..

One more qiestion- https://gateoverflow.in/2019/gate2014-2-52

 

---

@Verma Ashish

How so? If we consider unlabelled vertices; for a graph with 3 vertices and 3 edges, total number of Spanning Trees would be just 1, and not 2.

This will hold for any $n \geq 3$

Answer would be 1, then. I'm open to corrections, though :)

---

@JashanArora 

Take the graph given in answer.

---

@Verma Ashish

I did, sir. It has more than 1 Spanning Tree even if we consider the nodes unlabelled.

I do agree that the answer "3" is correct for labelled graphs

But if we consider it unlabelled, to give the minimum number of Spanning Trees which would fit the criteria

"every simple connected graph with n vertices and n edges"

don't we need to consider 3 vertices and 3 edges? (less than that isn't a simple graph).

And if we do consider 3 vertices and 3 edges for an unlabelled graph, it's Spanning Trees count would be 1, and not 2. Right?

 

I hope I'm not being annoying; thanks in advance!

---

Yes sir you are right..

For same question if nodes are unlabelled then m=1 will be answer.(largest value of m such that....m different spanning trees) 

(3 vertices, 3 edges) or for any n(>3) vertices and n edges, there will be atleast 1 spanning tree.. 

---

@Verma Ashish

Appreciate you taking your time out for this! ^_^

---

@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.