GATE CSE 1995 | Question: 22

Question

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

Comments

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\}$.