1.3k views

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).

edited | 1.3k views
0

@Satbir

@ankitgupta.1729

@techbd123

@imShreyas

I want to solve this by $\mathbf{PnC}$.

I know answer is $\mathbf 2$ only as I have verified it by drawing.

But with permuation, for $\mathbf 3$ we have $2-\textbf{choices}$ and for $4$ we again have $2$ choces.

$\therefore$ Ans $=2\times 2 = 4$

What's wrong here?

0
For 3 we have 1 choice.
0
We can take any $3$, isn't it??

So $2$ choice?
0
see the daigram in answer both 3 are taken , only 4 has 2 choices which are taken in diagram.
0
Oh, yes actually that was the mistake I was doing.

I was thinking that at one of point of time, i can take any of the $3$.

So, if this $3$ would not have come in the diagram again then it would have been two choices, right?

$2$ only.

$\{AB,BC,AE,BD\}$ and $\{AB,BC,AE,CD\}$.

by Boss (19.9k points)
edited