GATE CSE 1995 | Question: 22

Question

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

Comments

@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?

---

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?

---

The question is a bit ambiguous. It asks  for minimum spanning tree which is 13 for this graph. Whereas the answer they are expecting is for number of minimum cost spanning tree which is 2.

---

“Minimum Spanning Tree” directly means that we have to find a spanning tree which is of minimum cost. The question is not ambiguous.

@Human

Answer 1

$2$ only.

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