Graph theory Modified

Question

What is the maximum integer value m such that every simple connected graph with r vertices and r+2 edges contains at least m different spanning trees ?

1)1

2)4

3)8

4)m

Comments

@gauravkc just take r=4 and then edges =6

okk then form complete graph of 4 vertices.

then draw all spanning trees and see for many cases there is no cycle for remaining edges

---

:O I'm not getting how no cycle will be formed. A cycle can be of any length equal to or greater than 3. And every edge must be a part of a cycle after spanning tree is drawn as far as I know. Please correct me if wrong.

---

the minimum value of r is 4 because we cannot construct a simple graph with 3 vertex and 5 edges

when r=4 vertex is 4 and edges are 6 so there will atleast 16 spanning trees .

Answer 1

I am getting more than 8 spanning trees.

Comments

how many?

Answer 2

no of spanning tree eCa. where is e is edge and if n is vertices then a = e-n+1. now here e = r+2 and n = r . so by using this eCa we can get {(r+2)(r+1)r} / 6 . so now r = 0 is not possible so min value of r will be  1 , putting the value in r  m will be 1.

Comments

r=1 ===> no.of nodes=1

edges=r+2 = 1+2=3 ====> with 1 node and 3 edges is it simple graph form?