Distinct Edge Weights

Suppose we are given a connected, undirected, weighted graph. This is a graph $G = (V, E)$ together with a function $w: E \rightarrow \mathbb{R}$ that assigns a real weight $w(e)$ to each edge $e$, which may be positive, negative, or zero. This chapter describes several algorithms to find the minimum spanning tree of $\bold{G}$, that is, the spanning tree T that minimizes the function

$$w(T):=\underset{e \space\varepsilon\space T}{\sum}w(e).$$

Distinct edge weights

An annoying subtlety in the problem statement is that weighted graphs can have more than one spanning tree with the same minimum weight; in particular, if every edge in $G$ has weight $1$, then every spanning tree of $G$ is a minimum spanning tree, with weight $V − 1$. This ambiguity complicates the development of our algorithms; everything would be much simpler if we could simply assume that minimum spanning trees are unique.

Proof of the uniqueness of minimum spanning tree

Fortunately, there is an easy condition that implies the uniqueness we want.

Lemma: If all edge weights in a connected graph $G$ are distinct, then $G$ has a unique minimum spanning tree.

Proof: Let $G$ be an arbitrary connected graph with two minimum spanning trees $T$ and $T^′$; we need to prove that some pair of edges in $G$ have the same weight. The proof is essentially a greedy exchange argument. Each of our spanning trees must contain an edge that the other tree omits. Let $e$ be a minimum-weight edge in $T \backslash T^′$, and let $e^′$ ...