Skip to main content

MST, Cut Property, and Cycle Property

What This Concept Is​

A spanning tree of a connected, undirected graph G = (V, E) is a subgraph that is a tree and touches every vertex. A minimum spanning tree (MST) is a spanning tree of minimum total edge weight.

Two structural theorems govern every MST algorithm:

  • Cut property. For any non-trivial cut (S, V - S), the minimum-weight edge crossing that cut is safe to include in some MST. If edge weights are distinct, that edge is in every MST.
  • Cycle property. For any cycle C, the maximum-weight edge in C is safe to exclude from every MST. If weights are distinct, the maximum-weight edge of any cycle is in no MST.

Every MST algorithm is an efficient way to apply one of these two properties many times. Kruskal and Prim pick cut edges; reverse-delete picks cycle edges to drop. Boruvka is historically the first MST algorithm and picks the minimum edge out of each component in parallel; it is the conceptual parent of Kruskal and Prim.

Distinguishing the two classic algorithms:

  • Prim vs Kruskal. Both apply the cut property. Prim grows one tree and always cuts "in-tree vs out-of-tree." Kruskal grows a forest and at each step cuts whatever cut the next-lightest edge happens to cross. The difference is data structure (priority queue vs sorted list + union-find), not proof.

Why It Matters Here​

Once you have internalized the cut property, Kruskal and Prim stop being "two different algorithms" and become "two different ways to decide which cut to process next":

  • Kruskal. Sort edges by weight; repeatedly add the next edge unless it forms a cycle. Each added edge is the minimum crossing the cut that separates its two current components.
  • Prim. Grow a single tree from a root; repeatedly add the minimum-weight edge connecting the tree to the rest of the graph. That is exactly the cut between "in-tree" and "out-of-tree."

The cut and cycle properties also justify why arbitrary local choices (min edge on a cut, max edge on a cycle) are globally correct - a nontrivial fact without them. Almost every MST-like problem in downstream modules invokes one of these properties as a lemma.

Concrete Example​

Undirected graph with distinct weights:

Apply the cut property to the cut ({a}, {b, c, d}). The crossing edges are (a,b)=1 and (a,c)=3; the minimum is (a,b). So (a,b) is in the MST.

Apply the cut property to ({a, b}, {c, d}). Crossing edges: (a,c)=3, (b,c)=2, (b,d)=5. Min is (b,c)=2. Add it.

Apply again to ({a, b, c}, {d}). Crossing edges: (b,d)=5, (c,d)=4. Min is (c,d)=4. Add it.

MST total weight: 1 + 2 + 4 = 7. The cycle a -> b -> c -> a has maximum-weight edge (a,c)=3, correctly excluded - the cycle property corroborates.

Second example - a tie situation. If we change (a,c) to 2 so both (a,c) and (b,c) have weight 2, both properties still hold in the form "some MST contains the light cut edge" / "some MST excludes the heavy cycle edge," and we have two MSTs (one using (a,c), one using (b,c)), each with total weight 7.

Common Confusion / Misconceptions​

  • "MST = shortest-path tree." Different objects. The unique tree path between u and v in an MST is not generally the shortest path in the original graph. MST minimizes total tree weight; SSSP minimizes root-to-vertex path weights.
  • "MST requires distinct weights." Not for existence - MSTs exist for any weighted connected graph. Distinct weights guarantee uniqueness.
  • "The cut property means every MST contains the lightest cut edge." With ties it is only some MST. Algorithms that break ties deterministically pick one.
  • "Adding a safe edge cannot be wrong later." The cut property explicitly says the edge is safe - extending to an MST is always possible. That is the whole point of the greedy proof.
  • "MSTs are only for connected graphs." For disconnected graphs, you get a minimum spanning forest - one MST per component.

How To Use It​

To prove an MST algorithm correct:

  1. show that each edge it commits to is the minimum crossing some cut (Kruskal / Prim / Boruvka), or
  2. show that each rejected edge is the maximum on some cycle (reverse-delete).

To reason on a specific instance:

  1. name the cut and argue the edge added is lightest across it, or
  2. name the cycle and argue the rejected edge is heaviest in it.

To design a new MST-variant algorithm, apply the generalized framework: any "light edge on a cut" lemma is the scaffold; the efficient implementation is the bookkeeping.

Transfer / Where This Shows Up Later​

  • S3 (systems). Spanning-tree protocols in Ethernet (STP, RSTP) are literally MST-like but optimizing for loop-free topology rather than weight. Same cut-property proof underlies them.
  • S4 (compilers). Instruction-scheduling problems sometimes reduce to min-weight spanning structures on dependency graphs.
  • S5 (OS). Network-boot spanning trees, PTP clock distribution trees.
  • S6 (databases). Query plans sometimes contain "minimum-cost join tree" subproblems that are spanning-tree-adjacent.
  • S7 (DDD). Minimum-dependency-weight skeleton across a context map is an MST.
  • S8 (distributed). Multicast trees, broadcast trees, Chandy-Lamport snapshot spanning trees. Overlay networks pick MSTs over physical network costs.

Back-link to S1 M2 (tree definition) and to M4 greedy-algorithms for the exchange-argument correctness proof.

Check Yourself​

  1. State the cut property and the cycle property precisely.
  2. Why does "distinct weights" guarantee a unique MST?
  3. Why does the cut property only promise "some MST" rather than "every MST" in the general case?
  4. Give a graph and a spanning tree that is minimum-weight but not produced by Kruskal starting from edges sorted ascending (hint: think about ties).
  5. Prove the cut property using the exchange argument: assume an MST T does not contain the light cut edge, and produce a contradiction.
  6. Why does Boruvka's algorithm - pick the lightest edge out of each component in parallel - also produce an MST?

Mini Drill or Application​

On the graph

a - b (4), a - c (1), b - c (3), b - d (2), c - d (5), c - e (6), d - e (7)

use the cut property three times to build an MST, writing one sentence per application naming the cut and the added edge. Report the total weight.

Then verify the result by the cycle property: for each cycle present, check that the heaviest edge is excluded.

Implementation drill.

  1. Implement a generic MST solver that takes a "pick next safe edge" policy as a parameter; instantiate it as both Kruskal and Prim.
  2. On a graph with tied weights, confirm that different tie-breaking rules produce different but equal-weight MSTs.
  3. Implement Boruvka's algorithm (repeatedly add the minimum edge of each component until one tree remains) and verify it agrees.
  4. Prove in code: for a random MST T, for every non-MST edge (u, v), the maximum weight on the tree path from u to v is <= w(u, v). This is the cycle property as a test.

Read This Only If Stuck​