find out the no. of spanning tree possible

Question

How many spanning trees are possible from the graph given below?

• A. $24$
• B. $34$
• C. $44$
• D. $54$

Comments

Explain how u calculate number of graph with 3 length cycle.

---

plz explain this ques in detail bcoz i am unable to understand....

---

@digvijay Pandey

 The no of cycle of length 3 is 4

no of graph with 3 length cycle (may be disconnected) =  select any cycle of length  3 (select any small triangle) and then out of 6 vertices select any 2..= 4*6C2 =60

why u have taken 3*6C2 instead of 4*C2

pls explain

---

check out this https://gateoverflow.in/202571/spanning-tree

Answer 1

total 9 edges and 6 vertices..
for spanning tree we need 6 vertices and 5 edges..
no of graphs with 5 edges  : 9C5
no of graph with 3 length cycle (may be disconnected) =  select any cycle of length  3 (select any small triangle) and then out of 6 vertices select any 2..
= (6C2)*3 +  12(for middle triangle) = 57

find no of 4 length cycle = select 4 length cycle and for rest 1 edge select those edges which doesn't  produces 3 length cycle..
= 4 + 4 + 4 = 12

no of 5 length cycle = 3

total spanning tree = 126 - (57 + 12 + 3)
                                  = 126 - 72
                                  = 54

Comments

@ Digvijay Pandey

How possible no. of subgraph with the middle triangle is 12? Shouldn't this be 6C2? please explain.

---

@Akhilesh Yadav since, if we select the middle triangle, now we need to select more two edges, there are 3 ways to select two edges such that it will build another triangle which is already taken into account. so 15-3 =12

---

If combination forming for this question is getting difficult for someone...then...you can go with Kirchoff's algorithm also...the only disadvantage is it gets lengthy...but if you are fast with determinant calculations...then...this algo is simple and best!

For those who are facing difficulty ...with spanning tree questions..

Answer 2

i will use the same approach as i used here https://gateoverflow.in/262827/self-doubt-spanning-tree#a262893

i have numbered the node.

total edges are 9 .For mst edges will be v-1=5

step 1 : total combination

9c5=126

but this combination contains 3 edges,4edges,5 edges cycle.so subtraction from these must be done.

step 2: finding 3 edges cycle 

3 edges cycle are (123,245,235,356)- 4 cycles

now for each cycle 2 edges are remaining so choosing those 2 edges will take 6c2 ways.

total=4*6c2 

but if we choose 2 more edges then there may be chances of getting 4 edges cycle.

for example- in cycle 123 if we choose edge 5-3 and 2-5  cycle 1253 is possible,in cycle 235 if we choose 2-4 & 4-5 then 2354 is possible also in same cycle if we choose edge 3-6,5-6 then cycle  2365 is possible. 

3 EDGES CYCLE                                                      EDGES  ADDED                                     4 EDGES CYCLE FORMED

123                                                                 5-3,2-5                                                                      1253

245                                                                  2-3,3-5                                                                      2354

235                                                   5-4,2-4 or 3-6,5-6 OR 1-2,1-3                                2354 OR  2365 OR 1253

356                                                         2-5,2-3                                                                                 2365

so total 6 (4-edges cycle) will be formed so we must remove this 6 cycles 

4*6c2-6=54

case 3: finding 4 edges cycle (1253,2453,2563)

choosing the fifth edges will take 5c1 ways but we have to careful that choosing 5th edges can lead us to 5 edges cycle.

4 EDGES CYCLE                                                          EDGES ADDED                                       5 EDGES CYCLE

1253                                                                                 2-3                                                               231253

2453                                                                                  2-5                                                              253245

2563                                                                                  3-5                                                               356325

So 3 5EDGES WILL BE FORMED SO WE MUST REMOVE THESE 3 CYCLES  3*5c1-3=12       

case 4:choosing 5 edges cycle(231253,253245,532563,421354,521365,236542)

total 6 

 

final answer:126-(54+12+6)=54

 

 

 

 

 

Comments

@adarsh_1997 

one doubt : 

While considering 5 edge cycles... 3 are actual 5 edge cycles. But the rest what you took are 2 - 3 edge cycles with 1 edge common and which i guess are already covered in 3 edge cycles. isnt it ?

 

p.s : 

I got my mistake : 

Its like,  even if are repeating the cycles , it is still a different count coz it is formed during different edge count. 

is it fine ?

 

n yeah... nice approach (y)

---

@HeadShot yes bro. 

Answer 3

54 

https://gateoverflow.in/10154/find-out-the-no-of-spanning-tree-possible

Logic is that we know that spanning tree doesn't contain cycle.so we will find total graphs possible with n vertices and n-1 edges and then we will remove all graphs which contain cycle from it.In the question, there is 6 vertices and 9 edges. 

doubt about why only 12 graphs for the middle triangle? Because by choosing middle triangle we have selected 3 edges now we need 2 more edges, to select it there are 3 ways such that it will include already considered triangles i.e. repetition in terms of 3 triangles.

So 6c2 =15-3 =12

Comments

Can you please elaborate the above answer.