Redirected
edited by
4,176 views
3 votes
3 votes

How to approach such questions ? Please provide detailed solution. 

Answer given is option C

edited by

3 Answers

Best answer
12 votes
12 votes

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

selected by
4 votes
4 votes
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
Answer:

Related questions

3 votes
3 votes
0 answers
1
smsubham asked Jan 6, 2018
519 views
Am getting 7. The answer given is 10.A - B , A - D , D - E , E - C are the edges i have included.
2 votes
2 votes
0 answers
2
–1 votes
–1 votes
1 answer
3