in Graph Theory edited by
14,725 views
66 votes
66 votes

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 ?

  1. $1$
  2. $2$
  3. $3$
  4. $n$
in Graph Theory edited by
14.7k views

4 Comments

@Pratyush Priyam Kuan
In your graph, we have a cycle of length = 4.
So in the cycle we need to omit an edge to get the Spanning tree. (Think of it as no. of ways of omitting 1 edge, in our example it is 4C1 = 4).
And the edges which are not in the cycle need to be selected mandatorily, as we don't have any other edge to reach the vertex which is not in the cycle.

So finally the number of spanning trees = 4C1 * 1C1 = 4 * 1 = 4.
Let me know if anything is wrong here. :)

3
3

@Pratyush Priyam Kuan 

As per the question we need to find the minimum number of spanning tress. With n=5, You have made a graph that has 4 vertices in cycle. But if we have 3 vertices in cycle , we get the less spanning tree that is m =3.

0
0
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
0
0

6 Answers

87 votes
87 votes
Best answer

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.

edited by

4 Comments

@Prabhjeet6 , 

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

V{a, b, c, d} & G{ac, cd, bc, ad}

0
0
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
0
0

@ Simple connected graph can have a cycle.

0
0
16 votes
16 votes

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 3Cways 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.

1 comment

Very nice explanation
0
0
7 votes
7 votes
ans :D

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

1 comment

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
1
1
7 votes
7 votes

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.

3 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.
0
0
Me
Sir, here we can have 4 MST of 5 vertices graph
please correct me if I'm wrong

 

0
0
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.
0
0
Answer:

Related questions