edited by
21,350 views
73 votes
73 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$
edited by

6 Answers

Best answer
93 votes
93 votes

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

7 votes
7 votes
ans :D

starting from 3 vertices only we can do 3 edges so atleast 3 spanning trees
1 flag:
✌ Edit necessary (bluebone)
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.

Answer:

Related questions

76 votes
76 votes
5 answers
2
Kathleen asked Sep 21, 2014
25,056 views
Which of the following graphs has an Eulerian circuit?Any $k$-regular graph where $k$ is an even number.A complete graph on $90$ vertices.The complement of a cycle on $25...
57 votes
57 votes
3 answers
3
34 votes
34 votes
2 answers
4
Ishrat Jahan asked Nov 2, 2014
12,922 views
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$?$10$$11$...