11.3 Cycle Property

Problem

The cut property identifies edges that can safely be added to a minimum spanning tree. An equally important question is the reverse:

How can we identify edges that can safely be discarded?

In large graphs, many edges obviously appear unnecessary. If we can prove that certain edges never belong to any minimum spanning tree, we can eliminate them immediately and reduce the search space.

The cycle property provides exactly this criterion.

Solution

A cycle is a closed path that starts and ends at the same vertex without repeating edges.

Example:

A ----- B
|       |
|       |
|       |
D ----- C

This graph contains the cycle:

A → B → C → D → A

The cycle property states:

If an edge has strictly greater weight than every other edge in a cycle, then that edge does not belong to any minimum spanning tree.

This theorem is the dual of the cut property.

The cut property tells us which edges are safe to add.

The cycle property tells us which edges are safe to remove.

Visual Example

Consider:

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

Cycle edges:

(A,B) = 2
(B,C) = 3
(C,D) = 1
(D,A) = 4

The heaviest edge is:

(D,A) = 4

Since it is strictly heavier than every other edge in the cycle, the cycle property guarantees:

(D,A)

cannot appear in any minimum spanning tree.

We may remove it immediately.

Why the Property Works

Assume a minimum spanning tree (T) contains the heaviest cycle edge (e).

Removing (e) disconnects (T) into two components.

Since (e) belongs to a cycle, another edge (f) in the same cycle reconnects those components.

Because (e) is strictly heavier:

$$ w(f) < w(e) $$

Replace (e) with (f).

The graph remains:

Connected
Acyclic
A spanning tree

The total weight decreases.

This contradicts the assumption that (T) was minimum.

Therefore (e) cannot belong to any minimum spanning tree.

Example 1

Graph:

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

Cycle weights:

Maximum:

Edge:

(A,B)

By the cycle property:

(A,B)

never appears in a minimum spanning tree.

The remaining edges already connect all vertices:

(A,D)
(D,C)
(C,B)

Total cost:

$$ 2 + 1 + 4 = 7 $$

Example 2

Graph:

A ----- B
 \     /
  \   /
   \ /
    C

Weights:

(A,B) = 10
(A,C) = 3
(B,C) = 4

The cycle is the triangle.

Largest edge:

(A,B) = 10

Therefore:

(A,B)

cannot belong to any minimum spanning tree.

Optimal tree:

(A,C)
(B,C)

Weight:

$$ 3 + 4 = 7 $$

Strictly Greater Matters

Consider:

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

All edges have equal weight.

The cycle property does not apply.

No edge is strictly heavier.

Any two edges form a minimum spanning tree.

Three different minimum spanning trees exist.

This distinction is important.

The theorem requires:

$$ w(e) > w(f) $$

for every other edge in the cycle.

Greater-than-or-equal is insufficient.

Intuition

Imagine a cycle as a backup route.

If one road is more expensive than every alternative route around the cycle, that road is unnecessary.

Travel can always use the cheaper route.

Keeping the expensive edge only increases total cost.

Therefore the most expensive edge becomes redundant.

This intuition explains why cycles and spanning trees are closely related.

A spanning tree keeps connectivity.

Cycles represent redundancy.

The cycle property identifies the most expensive redundancy.

Relationship with the Cut Property

The two theorems are complementary.

Cut Property	Cycle Property
Finds edges to include	Finds edges to exclude
Uses cuts	Uses cycles
Chooses minimum crossing edge	Removes maximum cycle edge
Supports constructive algorithms	Supports elimination reasoning

Together they characterize minimum spanning trees.

Many correctness proofs alternate between these two viewpoints.

Application in Kruskal's Algorithm

Kruskal sorts edges by increasing weight.

When considering a new edge:

u ----- v

there are two possibilities.

Case 1: No Cycle Created

Add the edge.

Case 2: Cycle Created

Reject the edge.

Why?

Suppose all previously chosen edges have smaller or equal weight.

The newly considered edge is the heaviest edge in that cycle.

By the cycle property, it cannot improve the minimum spanning tree.

Therefore Kruskal safely discards it.

This observation explains why union-find works.

The data structure merely detects cycles.

The cycle property provides the mathematical justification.

Reverse Delete Algorithm

The cycle property leads directly to an alternative MST algorithm.

Algorithm

Sort edges in descending order.
Examine the largest remaining edge.
If removing it keeps the graph connected, remove it.
Otherwise keep it.
Continue until only (n - 1) edges remain.

Example

Graph:

Weight
8
7
6
5
4

Remove:

if connectivity survives.

Then:

and so on.

The algorithm repeatedly removes cycle-heavy edges.

It is essentially a direct implementation of the cycle property.

Proof Strategy Using Cycles

Many MST proofs follow the same structure:

Assume a solution contains a suspicious edge.
Find a cycle.
Identify a lighter alternative.
Exchange edges.
Produce a cheaper spanning tree.
Derive a contradiction.

This exchange argument appears throughout graph optimization.

Complexity Implications

The cycle property enables:

Edge pruning
Correctness proofs
Alternative MST algorithms
Efficient cycle-based reasoning

Without this theorem, algorithms would need much more expensive global analysis.

Instead, a local cycle inspection often determines whether an edge can ever be useful.

Common Mistakes

Ignoring the Strict Inequality

The theorem requires a unique heaviest edge.

Equal weights invalidate the conclusion.

Assuming Every Heavy Edge Can Be Removed

The edge must be the heaviest edge in a cycle.

A heavy bridge cannot be removed.

Confusing Cycles with Paths

The property applies only to closed cycles.

Ordinary paths provide no such guarantee.

Forgetting Connectivity

Removing an edge outside a cycle may disconnect the graph.

The theorem relies on the existence of an alternative route around the cycle.

Recipe

When analyzing a weighted graph:

Locate a cycle.
Find the maximum-weight edge in that cycle.
Check whether it is strictly heavier than every other edge.
If so, eliminate it from consideration.
Continue simplifying the graph.
Use the remaining edges to construct the minimum spanning tree.

The cycle property provides the exclusion rule for minimum spanning trees. Together with the cut property, it forms the theoretical foundation of Kruskal's algorithm, Prim's algorithm, Borůvka's algorithm, and many advanced network optimization techniques. The next section applies these principles directly in the first major minimum spanning tree algorithm: Kruskal's algorithm.