Self doubt Spanning tree

Question

How many numbers of spanning tree are possible?

Comments

@ Naveen Kumar 3

why you subtract $-3$ and $-2$

please answer this also, I'm not able to get the right answer.

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

and https://gateoverflow.in/261538/spanning-tree

---

If we choose A & choose 6c2 (we choose 1 common case of B), similarly for B-C & C-D, so I substracted 3

"-2" i did for 5 length cycle 12356 & 23456

---

I did mistake while calculating 4-length cycle there are 3 =>1256, 2346, 2345

& choosing 5c1 will contain already calculated parts 'AB', 'BC', 'CD'.

so, finally, $9c5$ - [4*($6c2$) - 3] - 2[($5c1$)-3] - 2 = 55.

Answer 1

just see this approach comment if anything wrong i did)

total edges=9  for mst number of edges must be in graph=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 (162,652,523,534)- 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 162 if we choose edge 6-5 and 2-5  cycle 1652 is possible,in cycle 625 if we choose 1-6 1-2 then 1652 is possible also in same cycle if we choose edge 5-3 2-3 then cycle 6532 is possible. 

3 EDGES CYCLE                                                      EDGES  ADDED                                     4 EDGES CYCLE FORMED

162                                                                   6-5 & 2-5                                                                     1652

625                                                          1-6,1-2 OR 2-3,5-3                                                              1652 &6532

235                                                            6-5,2-6 OR 5-4,3-4                                                              6532,5234

534                                                          2-5,2-3                                                                                        5234

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 (1652,6253,2345)

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

1652                                                                                     6-2                                                                 265216

6523                                                                                     2-5                                                                 253265

2345                                                                                       5-3                                                                532543

So 3*5c1-3=12       

case 4:choosing 5 edges cycle(123561,623456,253265,621652,352345)

total 5 

 

final answer:126-(54+12+5)=55

 

 

 

check this out .comment if anything wrong

Comments

@adarsh_1997

it seems right

please answer this also, I'm not able to get the right answer.

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

and https://gateoverflow.in/261538/spanning-tree

---

@lakshman patel     bro,what exactly problem you are having?

---

counting the $3$ length and $4$ length cycle?

---

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

CHECK THE ANSWER BRO. JUST POSTED

---

thanks

---

why are you considering same cycle twice in step 2:

eg:1652,6523