Thursday, June 28, 2012

Uniqueness of MST

Question : If no two edges of an undirected weighted graph have equal weights, prove that the Minimum Spanning Tree is unique.

Proof [1]:
First, let us state and prove the Cycle Property.

Statement [2]: "For any cycle C in the graph, if the weight of an edge 'e' of C is larger than the weights of other edges of C, then this edge cannot belong to an MST."

Proof :  Suppose e is a part of an MST, T. Removing e from T splits it into 2 connected components. There must be another edge e' in cycle C with one end in each connected components of T. Also, according to the hypothesis, the weight of e' is less than that of e. So, replacing e' with e in T results in a spanning tree of the graph with a smaller total weight than T, a contradiction. Q.E.D.

Now, suppose the given graph (G) has two different MST's, T1 and T2. Then, there exists and edge e1 in G which is a part of T1, but not of T2. Add e1 to T2. We get a cycle, C.  As all the edges of C, except e1, belong to T2, an MST of G, and since all edge weights are distinct, it follows from the cycle property that e1 is the unique maximum weight edge in C, which in turn implies that it cannot be a part of any MST of G. This is a contradiction, because e1 belongs to T1, which is assumed to be an MST of G. Q.E.D.

Notes :
[1] - This proof was the result of a discussion between Salman and me.
[2] - http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property

No comments:

Post a Comment