Ace Test Series: Graph Theory - Number Of Spanning Trees

Question

How to approach such questions ? Please provide detailed solution. 

Answer given is option C

Comments

Mk Utkarsh

why you closed this question...we both did in a different manner

there's not any option of merging the two same question with 2 answers ???

---

Magma Questions are closed if they are duplicate. I didn't merged the question. 

---

Image

Answer 1

Now the concept is

we have total 7 Edges and 5 vertices

and In spanning tree we know that no edges = |V| -1 = 4 right ??

Now from the 7 edges if we remove 3 edges in such a way that the graph doesn't contain any cycle

Condition one :  5C1 {Number of spanning tree possible doesn't contain BC and BD }

 

Condition 2 :  Number of spanning tree does contain BD edge

Here 2 cycles are formed {ABD} and {BDCE}

2C1 x 3C1 = 6 ways [2C1 -- > remove any edge from AD or AB ] [3C1 --- > remove any edge from {DC} or {CE} or {BE}]

Condition 3 : Number of spanning tree contain edges {BC}

2c1 x 3c1  = 6 ways

Condition 4 : Condition 3 : Number of spanning tree contain both  {BC} and {BD} edges

1C1 x 2C1 x 2 C1  -- > [we must have to remove DC ..because cycle is form therefore 1C1  & remove edge {AD} or {AB} by 2C1 or remove edge {BE} or {BC} required 2C1]

Add all the conditions

5 + 6 + 6 + 4 =21 Ans

Comments

Should be no... There should be some logic between every qyquesti of gate, I mean  90% gate questions are solved with in 3 minutes, remaining take 5-7min... If you very well in concept.

---

hmm for these questions if we know answers then by doing just some method here and there we can do this .

but if we dont know answers we will be struck after sometime. means never sure about them

---

Thank you @Magma

Answer 2

We can solve this question using Kirchoff's theorem but it will be time consuming because graph contains 5 vertices and that will result in 5 x 5 matrix.

We can solve this one with combinatorics easily.

Total Number of Vertices = 5
Total Edges = 7
Total Edges in MST = 4

Total possible combinations for MST = $C\binom{7}{4}$ = 35

Now we need to remove the cycles(cycles with 3 and 4 edges),

there can be 3 cycles (ABC,CBD,BDE) and for every cycle the fourth edge has 4 options

4 x 3 = 12.

We still have some invalid MST's and those are the ones with cycles with 4 edges

ABDC and BCDE

So total cycles with 4 edges = 12 + 2 = 14

Total MST's possible = 35 - 14 = 21

Comments

i check, but i not able to understand, what is mean by 4th edge have 4 option?

---

@lakshmanpatel

what is mean by 4th edge have 4 option?

always keep this in mind that you have take all graphs with V-1=4 edges(requirement of mst). now since we are talking about cycle with 3 edges(ABC,CBD,DBC). still one edges is left to be configured. now see the diagram shared by @mk utkarsh. for each cycle we can choose the 4th edge in 4 ways. so for three cycle it will be 4*3=12

---

@adarsh_1997

Yes 

i understand

Answer 3

Ans is 21