2.7 Uniqueness of the minimum spanning tree¶

Part 2 · Trees and paths · Chapter 2 · Chapter 2: Spanning trees · Lecture notes, volume 2 (PDF) · Exercises: Spanning trees · App: Minimum spanning trees: Kruskal and Prim

Theorem 2.15: distinct weights

If the weights \(w_e\), \(e \in E\), are pairwise distinct, the connected graph \(G=(V,E)\) has exactly one minimum spanning tree.

Proof

Assume that \(T_1 \neq T_2\) are minimum spanning trees. They have the same number of edges, so the symmetric difference \((T_1 \setminus T_2) \cup (T_2 \setminus T_1)\) is nonempty; let \(e\) be its lightest edge, and say \(e \in T_1 \setminus T_2\).

The cycle \(C(T_2,e)\) is not contained in the acyclic \(T_1\), so it has an edge \(f \notin T_1\); \(f \neq e\), and \(f \in T_2\), so \(f \in T_2 \setminus T_1\).
\(f\) is in the symmetric difference and \(f \neq e\), so \(w_f>w_e\), the weights being distinct.
\(T_2 \cup \{e\} \setminus \{f\}\) is a spanning tree (Lemma 2.5) of weight \(w(T_2)+w_e-w_f<w(T_2)\): a contradiction. □

With distinct weights, Kruskal's algorithm, Prim's algorithm from any start vertex and every execution of the generic greedy algorithm return the same tree.
On the reference graph, Prim's algorithm from \(s=6\) adds \(\{5,6\},\{4,5\},\{3,4\},\{1,3\},\{2,3\}\): once more the tree \(\tilde{F}\).

2.7.1 Weights with ties¶

Proposition 2.16: edges in every or in no minimum spanning tree

Let \(T\) be a minimum spanning tree of \(G=(V,E)\).

(a) An edge \(e \in T\) belongs to every minimum spanning tree if and only if \(w_e<w_f\) for every \(f \neq e\) in the fundamental cut of \(e\).
(b) An edge \(e \notin T\) belongs to no minimum spanning tree if and only if \(w_e>w_f\) for every \(f \neq e\) in \(C(T,e)\).

In particular, \(T\) is the unique minimum spanning tree if and only if every edge outside \(T\) is strictly heavier than the other edges of its fundamental cycle.

Proof

(a) If the inequalities hold, \(e\) is in every minimum spanning tree by the cut property (Theorem 2.6(b)). Otherwise some \(f \neq e\) in the fundamental cut has \(w_f \le w_e\), and \(w_f \ge w_e\) by the cut condition (Theorem 2.8): so \(w_f=w_e\), and \(T \cup \{f\} \setminus \{e\}\) is a spanning tree (Lemma 2.5(2)) of the same weight, without \(e\).
(b) If the inequalities hold, \(e\) is in no minimum spanning tree by the cycle property (Theorem 2.7(b)). Otherwise some \(f \neq e\) in \(C(T,e)\) has \(w_f=w_e\), by the cycle condition, and \(T \cup \{e\} \setminus \{f\}\) is a minimum spanning tree containing \(e\).

For the last claim: \(T\) is unique if and only if no edge outside \(T\) belongs to a minimum spanning tree, that is, (b) holds for every \(e \notin T\). □

Example 2.9: ties on the reference graph

Let \(w_{12}=3\) instead of \(4\), so that \(w_{12}=w_{23}=3\). The fundamental cycle of \(\{1,2\}\) in \(\tilde{F}\) is \(1,3,2,1\), with \(w_{23}=w_{12}\): by Proposition 2.16(b), the tree \(\{1,2\},\{1,3\},\{3,4\},\{4,5\},\{5,6\}\) is also optimal, with weight \(18\).
Enumeration confirms that these are the only two minimum spanning trees. Kruskal's algorithm, scanning \(\{1,2\}\) before \(\{2,3\}\), returns the one with \(\{1,2\}\).
Ties do not always create several optimal trees: with \(w_{35}=w_{46}=9\) the tree \(\tilde{F}\) is still the unique minimum spanning tree, because each of the four edges outside it remains strictly the heaviest of its cycle.

With distinct weights the minimum spanning tree is unique. With ties, a tree is the unique optimum if and only if every edge outside it is strictly the heaviest of its fundamental cycle.

2.8 Typical mistakes¶

Warning

Using the cut property with a cut crossed by \(F\). The lightest edge of \(\delta(S)\) is safe only if no edge already chosen crosses \(\delta(S)\).
Accepting an edge in Kruskal's algorithm because it touches a new vertex. The test is whether the two endpoints are in different components: \(\{3,4\}\) is accepted although both \(3\) and \(4\) are already covered.
Updating the labels in Prim's algorithm with path lengths. The new label is the weight \(w_{vu}\) of a single edge, not \(d(v)+w_{vu}\): that is Dijkstra's algorithm for shortest paths.
Forgetting that the labels can only decrease. In Prim's algorithm \(d(u)\) changes only when \(w_{vu}<d(u)\).
Claiming uniqueness from the algorithm. Kruskal and Prim return one tree; with ties other optimal trees may exist, and they are found through the equalities in the fundamental cycles.
Applying the algorithms to directed graphs. A minimum spanning tree is defined on undirected graphs; in a directed graph the orientation of the arcs is ignored.

2.9 In summary¶

In summary

A minimum spanning tree is a spanning tree of minimum total weight of a connected weighted graph; it has \(n-1\) edges.
Cut property: the lightest edge of a cut not crossed by \(F\) extends \(F\) within some minimum spanning tree. Cycle property: the heaviest edge of a cycle can be left out, and if it is strictly the heaviest it is in no optimum.
A spanning tree is optimal if and only if every edge outside it is the heaviest of its fundamental cycle, or equivalently every tree edge is the lightest of its fundamental cut.
Kruskal's algorithm sorts the edges and accepts those joining two components, in \(O(m\log n)\) time; Prim's algorithm grows one tree with the labels \(d(v)\), in \(O(n^2)\) time.
With distinct weights the minimum spanning tree is unique.

The weighted reference graph at a glance.

vertices, edges, spanning trees	\(n=6\), \(m=9\), \(55\)
minimum spanning tree	\(\{1,3\},\{2,3\},\{3,4\},\{4,5\},\{5,6\}\), weight \(18\) (unique)
Kruskal	accepts \(\{1,3\},\{4,5\},\{2,3\},\{3,4\},\{5,6\}\); rejects \(\{1,2\},\{2,4\}\)
Prim from \(1\)	selects \(3,2,4,5,6\)

Exercises on this chapter: Spanning trees