Dark Mode

4,077 views

12 votes

0

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

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

2

1

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..

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

1

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

edited
Jan 4, 2019
by HeadShot

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)

0

1 vote

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