Uniqueness of the minimum spanning tree
Task number: 4231
Show that if the edge weights are injective (as a function), then the minimum spanning tree is unique.
Solution
Let \( T \) be a minimal spanning tree and \( T ’\) be any other spanning tree. Select the \( e \) edge of the smallest weight from \( T ’\setminus T \).
By removing \( e = (u, v) \), the tree \( T’\) breaks down into two components \( C \) and \( C’ \). Each end of \( e \) is in a different one. On the other hand, in \( T \), \( u \) and \( v \) are connected by a path, so some edge \( f \) of this path connects \( C \) with \( C’\). Because \( T \) is minimal and the weights are different, \( f \) has smaller weight than \( e \).
By replacing \( e \) with \( f \) in \( T ’\) we get a sanning tree of smaller weight, so \( T’ \) is not minimal.
