Question

Show that there is a unique minimum spanning tree in a connected weighted graph if the weights of the edges are all different.

Short answer

The minimum spanning tree is unique when all edges have different weights.

Step-by-step solution

Definition

A graph is connected if there exists a path between every pair of vertices.

Prim's algorithm:

Start from a graph that contains only the vertices and no edges, select a root, add the edge from the root to another vertex with the smallest weight.Repeatedly add the edge from a vertex in the already constructed tree to another vertex (not yet included in the tree) with the smallest weight.Once the graph is connected, we have found a minimum spanning tree.

Proof by contradiction

Given: \(G\) is a connected weighted graph with \(n\) vertices

\(T\)is a minimum spanning tree of \(G\)

Weights of the edges in \(G\) are all different

To proof: \(T\) is unique

Proof by contradiction:

Let \(T\) and \(U\) both different minimum spanning trees, then these two trees need to have the same minimum total weight \(a\).

There exist an edge \({\bf{e = \{ u,v\} }}\) that is contained in \(T\) but not in \(U\) (which should be true if \(T\) and \(U\) are not the same tree and \(U\)and\(T\) both have \({\bf{n - 1}}\) edges).

Adding and removing edges

Adding \({\bf{e = \{ u,v\} }}\) to \(U\) will then lead to a circuit being formed in the new graph. Since there was no circuit in \(T\), there then exists an edge \({\bf{f = \{ w,x\} }}\) in that circuit that is not in \(T\), but is present in \(U\).

Since the weights of all edges in \(G\) are different, \({\bf{e}}\) and \({\bf{f}}\) have different weights. Let us assume that \({\bf{f}}\) has the smaller weight (if not, then apply the following to \(U\) instead of \(T\)).

If we then remove edge \({\bf{e}}\) from \(T\) and add edge \({\bf{f}}\) to \(T\), then the new tree \(T'\) is a spanning tree with a total weight less than \(a\). We have then derived a contradiction (as \(T\) was the minimum spanning tree) and thus \(T\) and \(U\) cannot be different minimum spanning trees, which implies that the minimum spanning tree is unique.