1,035 views
0 votes
0 votes

How many numbers of spanning tree are possible?

1 Answer

Best answer
7 votes
7 votes

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

selected by

Related questions

0 votes
0 votes
1 answer
2
atulcse asked Jan 13, 2022
476 views
How many minimum spanning trees are possible in this graph?
1 votes
1 votes
1 answer
3
Ram Swaroop asked Jan 30, 2019
1,563 views
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the...
0 votes
0 votes
0 answers
4