Skip to content

Cut and Cycle Property

Cycle property: heaviest edge in any cycle is not in MST

Cut property: lightest edge crossing a cut must be in MST

The Two Theorems Behind Every MST Algorithm

Kruskal's and Prim's produce the same tree. That's not a coincidence. Both algorithms are correct because of two structural properties of MSTs: the cut property and the cycle property. These are the theoretical foundation. Once you internalize them, MST problems stop being about memorizing algorithms and start being about recognizing which property applies.

What Is a Cut?

A cut of a graph is a partition of the vertices into two non-empty sets S and V-S. The cut edges are all edges with one endpoint in S and the other in V-S.

Think of drawing a line through the graph that separates some nodes from the rest. Every edge crossing that line is a cut edge.

The Cut Property

Theorem: For any cut of the graph, if there is a unique lightest edge crossing the cut, that edge is in every MST.

Proof sketch: Suppose the MST doesn't include the lightest crossing edge e. The MST must cross the cut somehow (it connects all nodes). So it uses some other crossing edge e' with weight >= weight of e. Remove e' from the MST. The tree splits into two components that happen to be on opposite sides of the cut. Add e back. The result is a spanning tree with equal or smaller weight. If e was strictly lighter, the original MST wasn't minimum. Contradiction.

💡 Key insight. The cut property is why Prim's works. At each step, Prim's considers the cut between "nodes in the tree" and "nodes not yet in the tree." It picks the lightest crossing edge. The cut property guarantees this edge belongs to some MST.

The Cycle Property

Theorem: For any cycle in the graph, if there is a unique heaviest edge in the cycle, that edge is in no MST.

Proof sketch: Suppose the MST includes the heaviest edge e of some cycle. Remove e from the MST. The tree splits into two components. Since e was part of a cycle, there's another edge e' in the cycle connecting those two components. e' is lighter than e (since e was the unique heaviest). Replace e with e' to get a cheaper spanning tree. Contradiction.

💡 Key insight. The cycle property is why Kruskal's works. When Kruskal's skips an edge, it's because adding that edge would create a cycle. That edge is the heaviest in that cycle (since all lighter edges were already added). The cycle property says it doesn't belong in any MST.

Visualizing Both Properties

Consider this 4-node graph:

    1 ---3--- 2
    |         |
    1         2
    |         |
    3 ---4--- 4

Edges: (1,2,3), (1,3,1), (2,4,2), (3,4,4).

Cut property example: Take the cut S = {1,3}, V-S = {2,4}. Crossing edges: (1,2,3) and (3,4,4). The lightest is (1,2,3). This edge must be in the MST.

Cycle property example: The cycle 1-2-4-3-1 has edges with weights 3, 2, 4, 1. The heaviest is (3,4,4). This edge is in no MST.

Proving Kruskal's Correctness

Kruskal's processes edges in order of increasing weight. For each edge (u,v,w):

  • If u and v are in different components, adding this edge is safe. Why? Consider the cut between u's component and everything else. This edge is the lightest crossing edge we haven't processed yet (all lighter ones were already added or rejected). By the cut property, it belongs in an MST.

  • If u and v are in the same component, adding this edge creates a cycle. This edge is the heaviest in that cycle (all other edges in the cycle were added earlier and have smaller weight). By the cycle property, it doesn't belong in any MST.

Proving Prim's Correctness

Prim's maintains a growing tree T. At each step it adds the cheapest edge connecting T to a non-T node.

The cut is (T, V-T). The edge Prim's chooses is the lightest crossing edge. By the cut property, this edge is in some MST. By induction, every edge Prim's adds is in some MST, so the final tree is an MST.

MST Uniqueness

Theorem: If all edge weights are distinct, the MST is unique.

Proof: Suppose two different MSTs exist: T1 and T2. Let e be the lightest edge in T1 that's not in T2. Adding e to T2 creates a cycle. Every other edge in this cycle is in T2, and since T1 chose e but T2 didn't, some edge e' in the cycle has weight > weight(e) (by distinctness). But then T2 could replace e' with e to get a cheaper tree, contradicting that T2 is an MST.

When weights aren't distinct: Multiple MSTs can exist. For example, a triangle with all edges having weight 1 has three different MSTs (each omitting one edge).

⚠ Gotcha. "MST is unique" and "MST weight is unique" are different statements. The MST weight is always unique (all MSTs have the same total weight), but the actual set of edges can differ when weights repeat.

MST Weight Is Always Unique

Even when multiple MSTs exist, they all have the same total weight. This follows from a stronger fact: if you sort the edge weights used by any MST, you get the same sorted sequence. This is called the MST weight sequence.

Practical Implications

Question Property to Use
Must this edge be in the MST? Find a cut where it's the unique lightest crossing edge
Can this edge be in some MST? Check if it's NOT the unique heaviest in any cycle
Is the MST unique? Check if all edge weights are distinct
Can I swap MST edges? Use the cycle property on the new edge's cycle

These questions come up constantly in MST problems. The cut and cycle properties give you the tools to reason about them without running the full algorithm.

Example: Deciding if an Edge Is in Every MST

Given edge (u,v,w), is it in every MST?

  1. Remove edge (u,v) from the graph.
  2. Find the shortest path from u to v in the remaining graph (or the min-weight max edge on the path in the MST).
  3. If the path's bottleneck weight > w, then (u,v) is in every MST (it's the unique lightest crossing edge for the cut that separates u's component when (u,v) is removed).
  4. If the path's bottleneck weight == w, it's in some MSTs but not all.
  5. If the path's bottleneck weight < w, it's in no MST.

💡 Key insight. "In every MST" means the edge is irreplaceable. "In some MST" means it's one of several equally-good options. "In no MST" means it's always suboptimal.

Try It

Consider this graph with 5 nodes and 7 edges:

Edges: (1,2,1), (1,3,2), (2,3,2), (2,4,3),
       (3,4,3), (3,5,4), (4,5,5)
  1. Find the MST. Is it unique?
  2. For edge (2,3,2): is it in every MST, some MSTs, or no MST?
  3. For edge (4,5,5): which property tells you it's excluded?

Answers: The MST uses edges with weights 1, 2, 3, 4 (total=10). Edge (2,3,2) ties with (1,3,2) -- MST is not unique. Edge (4,5,5) is the heaviest in cycle 3-4-5, so the cycle property excludes it.

Problems

Problem Link Difficulty
CSES Road Reparation cses.fi/problemset/task/1675 Easy