Minimum spanning tree

Question

In given graph G if only AC and BC belong to its minimum spanning tree, then what can be the minimum sum of weights of all edges in the graph G?

A. 13

B. 14

C. 20

D. 21

Comments

distinct integer edge weights then 21(AB is 10)
Else 20 (AB is 9)

In GATE question they will clearly mention which case to take.

https://gateoverflow.in/8313/gate2015-1-43

Answer 1

Here AB must be greater than AC and BC otherwise the edge AB must be included in the minimum spanning tree so to keep the weight of the tree minimum weight we have to take weight of AB as 10 so ans will be 10+9+2=21 answer D

But we may get same MST if  AB=AC = 9 also but that "may" so to ensure only 10 is taken

Comments

https://gateoverflow.in/8313/gate2015-1_43

---

Ans is 21 becouse question say that only AC AND BC