11.2 Cut Property

Problem

Minimum spanning tree algorithms repeatedly make local decisions. At each step, they select one edge from many available choices. The challenge is determining whether a locally attractive edge can safely become part of a globally optimal solution.

Suppose a graph contains thousands or millions of edges. Testing every possible spanning tree is computationally infeasible. We need a rule that identifies edges that must belong to some minimum spanning tree.

The cut property provides exactly such a rule.

Solution

A cut divides the vertices of a graph into two non-empty disjoint sets.

For example:

S = {A, B, C}

T = {D, E, F}

Every edge connecting a vertex in (S) to a vertex in (T) is called a crossing edge.

Example:

A ----- D
B ----- E
C ----- F

These are crossing edges because they connect opposite sides of the cut.

The cut property states:

For any cut in a connected weighted graph, the minimum-weight edge crossing that cut belongs to at least one minimum spanning tree.

This theorem is the foundation of nearly every minimum spanning tree algorithm.

Visual Example

Consider:

       2
   A ------ B
   |        |
  4|        |3
   |        |
   C ------ D
       1

Let:

S = {A, C}

T = {B, D}

Crossing edges:

(A,B) weight 2
(C,D) weight 1

The lightest crossing edge is:

(C,D) weight 1

The cut property guarantees that some minimum spanning tree contains edge:

(C,D)

without requiring us to examine every spanning tree.

Why the Property Works

Suppose we already have a minimum spanning tree (T).

Assume the lightest crossing edge (e) is not part of (T).

Because (T) connects all vertices, there must be a path between the endpoints of (e).

Adding (e) to (T) creates a cycle:

Tree + one extra edge = cycle

Since the cycle crosses the cut, at least one other edge in that cycle also crosses the cut.

Call that edge (f).

Because (e) is the lightest crossing edge:

$$ w(e) \le w(f) $$

Remove (f) and keep (e).

The graph remains connected.

The graph remains acyclic.

The total weight does not increase.

Therefore we obtain another minimum spanning tree containing (e).

This exchange argument proves the theorem.

Safe Edges

A safe edge is an edge that can be added without destroying the possibility of obtaining a minimum spanning tree.

The cut property identifies safe edges automatically.

Whenever an edge is the minimum-weight edge crossing some cut, it is safe.

This idea drives Kruskal's algorithm, Prim's algorithm, and Borůvka's algorithm.

Example 1

Graph:

      5
 A -------- B
 |          |
 |          |
2|          |4
 |          |
 C -------- D
      3

Choose cut:

S = {A}

T = {B,C,D}

Crossing edges:

(A,B) = 5
(A,C) = 2

Smallest crossing edge:

(A,C) = 2

The cut property says:

(A,C)

belongs to some minimum spanning tree.

No optimization search is necessary.

Example 2

Graph:

      7
A -------- B
| \        |
|  \       |
1   2      5
|    \     |
|     \    |
C -------- D
      3

Cut:

S = {A,C}

T = {B,D}

Crossing edges:

(A,B) = 7
(A,D) = 2
(C,D) = 3

Minimum crossing edge:

(A,D) = 2

Therefore:

(A,D)

is safe.

Building Intuition

Think of the cut as a border separating two countries.

Any spanning tree must contain at least one road crossing that border.

Otherwise the graph becomes disconnected.

Among all possible roads crossing the border, choosing the cheapest one is always safe.

Choosing a more expensive road can never improve the total cost.

This simple observation becomes extremely powerful when applied repeatedly.

Connection to Kruskal's Algorithm

Kruskal processes edges from smallest to largest.

Suppose the current forest contains several connected components:

Component 1
Component 2
Component 3

The next accepted edge connects two different components.

These components define a cut.

The selected edge is the smallest edge crossing that cut.

By the cut property, the edge is safe.

Thus every edge accepted by Kruskal is justified by the cut property.

Connection to Prim's Algorithm

Prim maintains:

Visited vertices
Unvisited vertices

These sets define a cut.

The algorithm selects the cheapest edge crossing that cut.

Again, the cut property guarantees safety.

Every step of Prim is therefore justified by the same theorem.

Multiple Minimum Edges

Sometimes several crossing edges have the same minimum weight.

Example:

(A,B) = 1
(A,C) = 1
(A,D) = 1

All are minimum crossing edges.

The cut property guarantees that at least one belongs to a minimum spanning tree.

In many graphs, multiple minimum spanning trees exist.

Different choices can produce different but equally optimal solutions.

Complexity Implications

The cut property itself is a theorem, not an algorithm.

However, it transforms a global optimization problem into a sequence of local decisions.

Without the cut property:

Search all spanning trees

With the cut property:

Repeatedly choose safe edges

This reduces the problem from exponential search to polynomial-time algorithms.

Common Mistakes

Choosing a Locally Small Edge Without a Cut

The edge must be the smallest crossing edge of some cut.

Being merely "small" is insufficient.

Ignoring Connectivity

The cut property assumes a connected graph.

Disconnected graphs require minimum spanning forests.

Confusing Safe with Mandatory

The theorem states:

The edge belongs to some minimum spanning tree.

Not necessarily every minimum spanning tree.

Forgetting Equal Weights

Equal-weight edges may produce multiple optimal solutions.

The theorem still holds.

Recipe

When analyzing a minimum spanning tree algorithm:

Identify a cut.
Find all edges crossing the cut.
Locate the minimum-weight crossing edge.
Mark that edge as safe.
Add it to the growing solution.
Repeat until (n-1) edges have been selected.

This principle is the central theorem behind minimum spanning trees. The next section introduces the complementary result, the cycle property, which explains which edges can safely be discarded.