The Gateway to Computer Science Excellence
+9 votes

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

in Algorithms by Veteran (52.2k points)
edited by | 1.3k views





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?

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

So $2$ choice?
see the daigram in answer both 3 are taken , only 4 has 2 choices which are taken in diagram.
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?

1 Answer

+24 votes
Best answer

$2$ only.

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


by Boss (19.9k points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,337 answers
105,203 users