CODEWITHSUNDEEP
data-structuresgraphcutminimum-spanning-tree
Tuhin Dutta
Tuhin Dutta

Reputation: 49

Distinct minimum spanning tree

For a connected, weighed, undirected graph G: G has a unique MST, if for every cut of G there is a unique minimum weight edge crossing the cut.

Is this statement true?

I think false because for the following graph in the given link there can be multiple MSTs.

https://drive.google.com/file/d/1yDK3juPxeDBdS-aEOx0aAsphy4odZ55l/view?usp=drivesdk

Upvotes: 0

Views: 778

Answers (1)

Heying Yu
Heying Yu

Reputation: 31

If you mean a connected graph G, with edge costs that are all distinct. Then G has a unique minimum spanning tree.

proof: Suppose there are two different MSTs, call them T1 and T2, who have different sets of edges--{t11, t12, … t1n-1} for T1 and {t21, t22, … t2n-1} for T2. So, let ti be the edge with the smallest weight only in T1 (not in T2). Since it is the smallest, ti must be included in "every choice" of MST. That is, both MST of T1 and T2 would have it. But this contradicts the definition of ti.

Upvotes: 1

Related Questions