edited by
21,366 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

1 votes
1 votes

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

–2 votes
–2 votes
The first thing is 'A graph(simple, connected) containing same number of edges as of vertices would for sure have just one cycle of length 3 or more..so to tell max number of spanning trees with n edge and n vertices graph we can take counter example as

Graph that is cycle of length 3(e=3,v=3) =>3 spanning tree

Graph that is cycle of length 4 (e=4,v=4)=> 4 spanning tree....

So answer would be 'n'.....
Answer:

Related questions

76 votes
76 votes
5 answers
2
Kathleen asked Sep 21, 2014
25,076 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,927 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$...