Trees · Minimum Spanning Tree

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Theorem (cut property). Let the edges of a set \(X\) be part of the minimum spanning tree of a graph \(G=(V,E)\). Let \(S \subseteq V\) be a set of vertices such that none of the edges in \(X\) connects \(S\) and \(V \setminus S\). Finally, let \(e\) be the lightest edge connecting \(S\) and \(V \setminus S\). Then \(X \cup \{e\}\) is part of some minimum spanning tree.

Proof. Let \(T\) be a minimum spanning tree, containing all edges from \(X\). It may not contain \(e\) (if it does, everything is proven). In this case, the endpoints of edge \(e\) are connected by some path in \(T\), which together with \(e\) forms a cycle. Since \(e\) crosses the cut, there is also another edge \(e'\), crossing the cut (crossing to the other side of the cut, we must return back). This edge lies in the tree \(T\).

Replacing \(e'\) with \(e\) in this tree gives a connected graph with the same number of edges, meaning it is also a tree. We obtain a new spanning tree, which is no worse than the old one (the weight of \(e'\) is not less than the weight of \(e\), which was assumed to be minimal among all edges crossing the cut) and contains \(X\cup\{e\}\), which was required. (Note that the removed edge \(e'\) crossed the cut and therefore could not be in \(X\).)◼