retagged by
4,672 views
11 votes
11 votes

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

  1. $24$
  2. $34$
  3. $44$
  4. $54$
retagged by

3 Answers

9 votes
9 votes
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
5 votes
5 votes

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

 

 

 

 

 

1 votes
1 votes

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

Answer:

Related questions

4 votes
4 votes
1 answer
1
Rohan Mundhey asked Nov 11, 2016
1,263 views
Consider the following adjacency matrix representation of connected graph then find the number of spanning trees are possible for the given graph$\begin{bmatrix} 0&1&1&1&...
7 votes
7 votes
2 answers
3
Lakshman Bhaiya asked Jan 15, 2018
5,998 views
Consider a complete bipartite graph with ‘m’ and ‘n’ vertices. If m = 4, n = 4, then the number of spanning trees of graph are ________.
1 votes
1 votes
1 answer
4
Ram Swaroop asked Jan 30, 2019
1,561 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...