Minimum spanning trees and the cut property

Prerequisites: Undirected graphs, connected components, and sorted edges.

Learning objectives

• Apply the cut property with explicit assumptions.
• Trace Kruskal’s algorithm and cycle rejection.
• Distinguish a spanning tree from a shortest-path tree.

A different optimization problem

For a connected, undirected weighted graph, a spanning tree connects every vertex using exactly V−1 edges and contains no cycle. A minimum spanning tree minimizes the sum of its edge weights. It does not necessarily minimize the distance from any chosen source to every other vertex. Confusing these objectives leads to plausible but incorrect network designs.

A cut partitions the vertices into two nonempty sets. An edge crosses the cut if its endpoints lie on opposite sides. The cut property says that a minimum-weight crossing edge can be included in some minimum spanning tree, provided the cut respects the edges already chosen by the algorithm. Ties can allow several different minimum trees with equal total weight.

The exchange argument

Take an optimal tree T that lacks the selected light crossing edge e. Adding e creates one cycle. That cycle contains another crossing edge f, because it must leave one side of the cut and return. Since e is a minimum crossing edge, weight(e)≤weight(f). Remove f. The result is again a spanning tree and is no more expensive than T. This proves existence of an optimum containing e; it does not assert that every optimum contains e.

Trace Kruskal’s algorithm

Kruskal processes edges in nondecreasing weight, accepting an edge only when it joins two different current components. For edges AB:1, BC:2, AC:3, CD:4, BD:5, it accepts AB then BC. AC would close a cycle inside component {A,B,C}, so it is rejected. CD connects D and is accepted. The final tree has weight 1+2+4=7.

A disjoint-set structure supports the component queries. Initially every vertex is its own set. An accepted edge unions its endpoints’ sets. Path compression and union by rank or size make these operations extremely efficient amortized, but edge sorting still contributes O(E log E) to the standard implementation. If the graph is disconnected, the same procedure produces a minimum spanning forest rather than one spanning tree.

Inspect the modeling assumption

Negative edge weights are acceptable for minimum spanning trees; the algorithm’s exchange proof does not require nonnegative weights. Direction is different: a directed network is not the same problem. Capacity, reliability, redundancy, and maximum-hop requirements also change the optimization task. A tree has no redundant route after any tree edge fails, even if its total construction cost is optimal.

To test an implementation, verify connectedness, acyclicity, edge count, and reported cost independently. On tiny graphs, enumerate candidate trees and compare totals. MIT’s algorithm notes connect the cut argument to greedy correctness. The central skill is to identify the exchange that preserves feasibility, not simply to sort edges and hope.

Practice problem

For vertices A,B,C,D, use undirected edges AB:1, AC:4, BC:2, BD:6, CD:3. Trace Kruskal and give its total weight. Then construct a shortest-path tree from A and compare the two objectives. Finally change CD to weight −3 and recompute the minimum spanning tree.

Worked solution

Kruskal accepts AB:1, BC:2, and CD:3, giving total 6; AC and BD are unnecessary once all vertices are connected. From A, shortest distances are B=1, C=3 via B, and D=6 via B,C, so this particular graph happens to permit the same tree for both objectives. That agreement is an example, not a general theorem: adding edge AD:5 makes the shortest path to D use AD while the minimum spanning tree remains AB,BC,CD with total 6. If CD becomes −3, Kruskal accepts it first, then AB and BC; the total is 0. Negative weights do not break the cut argument.

Check your understanding

A cut has two tied minimum-weight crossing edges. What does the cut exchange argument justify for either chosen edge?

• It occurs in every minimum spanning tree.
• Both tied edges must be selected together.
• Some minimum spanning tree can contain it.
• It lies on every shortest path across the cut.

Explanation

Adding a light edge and removing an appropriate crossing edge cannot increase cost. Ties do not imply membership in every optimum.

An undirected graph has 8 vertices and 3 connected components. How many edges does its minimum spanning forest contain?

• 3
• 5
• 8
• 7

Explanation

Each component with vi vertices contributes vi−1 edges, totaling 8−3=5.

Primary reading

• Introduction to Algorithms: lecture notes: MIT OpenCourseWare

Open the study and save your work →