Prove that a connected graph with unique edge weights has ex

Prove that a connected graph with unique edge weights has exactly one MST. (Hint: See

the proof of correctness for Kruskal’s algorithm.)

Solution

Definition of Minimum Spanning Tree (MST) is as follows:

The edges in tree T must connect all nodes of graph G and contain no cycle.

If graph G has a cycle, then there is more than one spanning tree for G.

The minimum spanning tree sorts all the edges in increasing order of cost. And add to T in this order as long as it does not create a cycle.

Correctness of Kruskal’s Algorithm:

A set T of edges of G is promising after stage i if T can be expanded to an optimal spanning tree for G using edges from That is, T is promising after stage i if there is an optimal spanning tree such that T T

Proof of graph with unique weights has exactly one MST:

Theorem:

If G= (V, E) is a graph with unique edge weights, and if G has two different spanning trees S= (V, ES) and T= (V, ET), then there is a third spanning tree T’ (possibly equal to S or T) such that either W (T’) < W (S) or W (T’) < W (T).

Proof:

Let G= (V, E) be a graph with unique edge weights. Suppose S= (V, ES) and T= (V, ET) are two distinct spanning trees for G. Let US=ES-ET, and UT=ET-ES. Since S and T are different, ESET. Since |ES|=|ET|, US , and UT . Since G has unique edge weights, there is an edge e US UT of maximum weight.

Without loss of generality, assume that e UT. Let = (V, ET-{e}). has two connected components C1 and C2. Since S is connected, S must contain an edge from a vertex u in C1 to a vertex v in C2. Furthermore, (u, v) must be an element of US, otherwise T would contain a cycle. Since (u, v) is an element of US, the weight of (u, v) must be less than the weight of e. Let T’= (V, ET-{e} {(u, v)}). T’ is a spanning tree of G, and W (T’) = W (T)-W (e) +W ((u, v)) < W (T).n

Proof 1:

If G=(V,E) has unique edge weights, and G has two different spanning trees S=(V,ES) and T=(V,ET), and W(S)=W(T) then there is a third spanning tree T’ of G not equal to either S or T such that W(T’) < W(T).

By the main theorem, T’ must exist and have a weight strictly smaller than one of S and T. Since S and T are of the same weight, the weight of T’ must be less than both. Since the weight of T’ is less than the weight of S or T, T’ cannot be equal to S or T

Proof 2:

If G= (V, E) has unique edge weights then G has a unique minimum spanning tree.

If there were two minimum spanning trees S and T, and S and T were different, then by proof 1 there must be a third minimum spanning tree T’ whose total weight is less than that of S or T. Since the weight of S and T is minimal, this is impossible, therefore the minimum spanning tree of G must be unique.