The Cut Property And Its Exchange Proof

Why a Cut Can Certify an Edge

A spanning tree must connect the two sides of every nontrivial cut. This simple constraint lets us identify edges that can safely appear in a minimum spanning tree: if an edge is lightest among those crossing a cut, exchanging it for another crossing edge cannot increase the tree's total weight. If it is the unique lightest crossing edge, the exchange instead strictly decreases the weight of any spanning tree that omits it.

Throughout, \(G=(V,E)\) is a finite, connected, simple graph with a real weight \(w(e)\) assigned to each edge. A spanning tree is a connected, acyclic subgraph containing every vertex. Its weight is the sum of its edge weights; a minimum spanning tree (MST) is a spanning tree of least weight. An MST exists: connectedness gives a spanning tree, there are finitely many spanning trees, and a finite nonempty set of real weights has a minimum.

Definition: A nontrivial cut is a partition \((S,V\setminus S)\) with \(\varnothing\ne S\ne V\). An edge crosses the cut if one endpoint is in \(S\) and the other is in \(V\setminus S\). Since \(G\) is connected, every nontrivial cut has at least one crossing edge. A lightest crossing edge is one whose weight is minimum among all edges crossing that cut.

The cut property concerns a particular cut and the edges crossing it. “Lightest” permits a tie: several crossing edges may attain the same minimum weight. The conclusion in that case is that each such edge belongs to some MST, not necessarily to every MST.

The Exchange Behind the Property

Lemma (Tree exchange): Let \(T\) be a spanning tree of a connected graph, and let \(e\) be an edge of the graph not in \(T\). Adding \(e\) to \(T\) creates exactly one cycle. Removing any edge \(f\ne e\) on that cycle leaves a spanning tree.

Proof. Write \(e=uv\). Since \(T\) is connected, it contains a path from \(u\) to \(v\); that path is unique, because two different paths between the same vertices would contain a cycle in \(T\). Adding \(e\) closes this path into a cycle. Every cycle in \(T+e\) must contain \(e\), since \(T\) itself has no cycles; after removing \(e\), such a cycle would be a \(u\)-\(v\) path in \(T\), which must be the unique path already identified. Thus the cycle is unique. Now let \(f\ne e\) lie on that cycle. Removing \(f\) leaves the graph connected: any route that used \(f\) can instead use the rest of the cycle to get between \(f\)'s endpoints. The remaining graph has no cycle, since any cycle in it would also be a cycle in \(T+e\), and the unique such cycle used \(f\). It is therefore connected and acyclic, and still contains every vertex; hence it is a spanning tree. \(\square\)

This exchange gives the cut property. The key point is that if an added edge crosses the cut, the tree path between its endpoints must also cross the cut. At least one edge on that path is therefore available to remove.

Theorem (Cut property): Let \(G\) be a finite, connected, simple weighted graph, and let \((S,V\setminus S)\) be a nontrivial cut. Every minimum-weight edge crossing the cut belongs to some MST. If a crossing edge is uniquely lightest, it belongs to every MST.

Proof. Let \(e=uv\) be a lightest edge crossing the cut, and choose an MST \(T\). If \(e\in E(T)\), then \(T\) already contains the required edge. Otherwise, add \(e\) to \(T\). By the tree-exchange lemma, this creates a unique cycle consisting of \(e\) and the path in \(T\) from \(u\) to \(v\). The path starts on one side of the cut and ends on the other, so at least one of its edges, say \(f\), crosses the cut. Since \(f\in E(T)\), it is different from \(e\). The lightest-edge assumption gives \(w(e)\le w(f)\). Remove \(f\) after adding \(e\). The result is a spanning tree \(T'\), and its weight is \(w(T')=w(T)-w(f)+w(e)\le w(T)\). Since \(T\) is already minimum, \(T'\) cannot have smaller weight, so it too is an MST. It contains \(e\), proving the first claim.

For the second claim, suppose \(e\) is uniquely lightest and assume for contradiction that some MST \(T\) omits \(e\). The same path-and-exchange argument finds an edge \(f\in E(T)\) crossing the cut. Because \(e\) is the unique lightest crossing edge, \(w(e)<w(f)\). Therefore the exchanged spanning tree satisfies \(w(T')=w(T)-w(f)+w(e)<w(T)\), contradicting that \(T\) is an MST. Thus every MST contains \(e\). \(\square\)

Worked Examples

Worked Example: A Unique Lightest Edge Across a Cut

Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,14,13\}\), with weights \(w(12)=1\), \(w(23)=2\), \(w(34)=3\), \(w(14)=4\), and \(w(13)=5\). Consider the cut \((\{1,2\},\{3,4\})\). Its crossing edges are \(23,13,14\), with weights \(2,5,4\), respectively. Thus \(23\) is uniquely lightest and the theorem says every MST contains it.

For a direct check, the three edges \(12,23,34\) form a spanning tree: they connect all four vertices and contain no cycle. Its weight is \(1+2+3=6\). To verify that this is minimum independently, list all three-edge subsets, since a tree on four vertices has three edges. The subsets \(12,23,13\) and \(34,14,13\) are disconnected. The other eight subsets are spanning trees, with weights \(6,7,8,9,10,9,10,11\), respectively. The minimum is \(6\), attained by \(\{12,23,34\}\), which contains \(23\).

Check: The cut-crossing weights are \(w(23)=2\), \(w(13)=5\), and \(w(14)=4\); hence \(23\) is indeed the unique minimum. In the listed spanning-tree weights, \(6\) is the smallest, so the example's MST and the cut-property conclusion agree.

Worked Example: Tied Lightest Edges

Let \(V=\{a,b,c,d\}\) and \(E=\{ab,cd,ac,bd\}\), with weights \(w(ab)=0\), \(w(cd)=0\), \(w(ac)=1\), and \(w(bd)=1\). Use the cut \((\{a,b\},\{c,d\})\). Its crossing edges are \(ac\) and \(bd\), both of weight \(1\). Each is a lightest crossing edge, so each belongs to some MST; uniqueness is not available to conclude that either belongs to every MST.

The graph is the cycle \(a,b,d,c,a\). Removing any one cycle edge leaves a spanning tree. Omitting \(ac\) gives the tree \(\{ab,cd,bd\}\), of weight \(0+0+1=1\). Omitting \(bd\) gives \(\{ab,cd,ac\}\), also of weight \(0+0+1=1\). Omitting \(ab\) gives \(\{cd,ac,bd\}\), of weight \(0+1+1=2\), and omitting \(cd\) gives \(\{ab,ac,bd\}\), also of weight \(0+1+1=2\). These are all four three-edge subsets; the first two are minimum spanning trees.

Check: Each listed subset is obtained by omitting one edge of the four-cycle, so it is connected and acyclic. The minimum weight is \(1\), and there are two MSTs: one contains \(bd\) but not \(ac\), while the other contains \(ac\) but not \(bd\). Thus both lightest crossing edges occur in some MST, but neither is in every MST.

Worked Example: An Edge Forced Into Every Minimum Spanning Tree

Let \(V=\{p,q,r,s\}\) and \(E=\{pq,rs,pr,qs,ps,qr\}\), with weights \(w(pq)=0\), \(w(rs)=0\), \(w(pr)=1\), \(w(qs)=2\), \(w(ps)=2\), and \(w(qr)=3\). For the cut \((\{p,q\},\{r,s\})\), the crossing edges are \(pr,qs,ps,qr\), with weights \(1,2,2,3\). Thus \(pr\) is uniquely lightest.

The edges \(pq,rs,pr\) form a spanning tree, with total weight \(0+0+1=1\). Any spanning tree must have at least one edge crossing this cut; otherwise it could not connect a vertex in \(\{p,q\}\) to one in \(\{r,s\}\). If a spanning tree omits \(pr\), every edge it uses to cross the cut has weight at least \(2\). All other edge weights in this example are nonnegative, so such a tree has total weight at least \(2\). The displayed tree has weight \(1\), so no tree omitting \(pr\) can be an MST. This verifies directly that \(pr\) is in every MST.

Check: The three edges \(pq,rs,pr\) connect all four vertices without a cycle, and their weight is \(1\). Every alternative crossing edge has weight at least \(2\), so any spanning tree that omits \(pr\) weighs at least \(2>1\), as the theorem predicts.

How to Use the Property

The cut property is a certificate about an edge, not a procedure for selecting all the edges of an MST. To apply it, specify a nontrivial cut, compare the weights of all edges crossing that cut, and then use the correct conclusion:

If an edge is lightest but tied with other crossing edges, it belongs to at least one MST.
If an edge is uniquely lightest, it belongs to every MST.
If an edge is not lightest across the chosen cut, this theorem gives no inclusion guarantee for it.

The cut does not have to be determined by weights, and it may be any nontrivial partition of the vertices. A useful cut is one for which the crossing edges are easy to identify or compare. The exchange proof explains why the guarantee holds: if a chosen MST omits a lightest edge, replacing a crossing edge on the resulting cycle preserves a spanning tree without increasing its weight.

Common Pitfall: Confusing “Some” with “Every”

A common error is to conclude that every lightest edge across a cut belongs to every MST. In the tied-edge example, the crossing edges \(ac\) and \(bd\) both have minimum weight \(1\). The calculation \(\{ab,cd,bd\}\), of weight \(1\), is an MST that omits \(ac\); the calculation \(\{ab,cd,ac\}\), also of weight \(1\), is an MST that omits \(bd\). The correct conclusion is that each tied edge belongs to some MST. The stronger conclusion about every MST requires a unique lightest crossing edge: the strict inequality \(w(e)<w(f)\) then makes an exchange strictly improve any tree that omits \(e\).

Check Your Understanding

For each question, distinguish carefully between a minimum crossing edge and a uniquely minimum crossing edge.

In a connected weighted graph, why must a spanning tree contain at least one edge crossing each nontrivial cut?
When a non-tree edge is added to a spanning tree, why is there exactly one cycle?
A cut has crossing-edge weights \(2,2,5\). What does the cut property guarantee about either edge of weight \(2\)? What does it not guarantee?
A cut has crossing-edge weights \(-1,0,3\). Explain why the edge of weight \(-1\) belongs to every MST.
In the tied-edge example, list the two minimum spanning trees and their weights. Which lightest crossing edge does each omit?