Minimum Spanning Trees

The problem we’re solving

You’re given a connected, undirected, weighted graph $G = (V, E)$, where each edge $e \in E$ has a weight $w(e)$ (cost, length, time, etc.). You want to pick some edges so that:

1. 1)Every vertex is connected (the chosen edges span all vertices).
2. 2)There are no cycles (so you’re not paying for redundant loops).
3. 3)The total weight is as small as possible.

A spanning tree is exactly a connected, acyclic subgraph that includes all vertices. So an MST is the best (minimum-weight) spanning tree.

What “tree” implies (and why it matters)

A spanning tree on $|V| = n$ vertices always has exactly $n-1$ edges. This is a powerful constraint:

• •If you have fewer than $n-1$ edges, you can’t be connected.
• •If you have $n$ or more edges and you’re connected, you must have a cycle.

So an MST is “choose $n-1$ edges carefully.”

A small example to ground the idea

Suppose you have 4 vertices and weighted edges:

• •$A\text{—}B:1$, $B\text{—}C:2$, $A\text{—}C:3$, $C\text{—}D:1$, $B\text{—}D:4$

One spanning tree is $(A,B),(B,C),(C,D)$ with weight $1+2+1=4$.

Another spanning tree is $(A,C),(C,D),(A,B)$ with weight $3+1+1=5$.

The MST would choose the first: total 4.

What MST is not

• •It’s not a shortest path tree (that’s rooted at one source and minimizes distances from the root).
• •It’s not about minimizing the maximum edge on every path (that’s related, but different objectives exist).

Existence and uniqueness

• •If the graph is connected, an MST always exists.
• •If all edge weights are distinct, the MST is unique.
• •If there are ties, there can be multiple MSTs with the same total weight.

Why greedy algorithms work here

Most graph optimization problems don’t allow “just keep taking the cheapest available step.” MST is special: it has local rules (cut/cycle properties) that certify a greedy choice won’t block optimality.

That’s the real theme of MST: we need a proof tool that justifies greedy growth.

Motivation: how can we “certify” an edge is a good idea?

If we’re building a spanning tree and we add an edge too early, we might later regret it. So we want a condition that says:

“No matter what the optimal MST looks like, there exists an MST that contains this edge.”

Such an edge is called safe.

Cuts: a clean way to reason about connectivity

A cut is a partition of vertices into two non-empty sets:

• •$S \subset V$
• •$V \setminus S$

An edge crosses the cut if it has one endpoint in $S$ and the other in $V \setminus S$.

Intuition: if your current partial structure has connected everything in $S$ and you want to connect to the outside, you must pick some edge that crosses the cut.

The Cut Property (statement)

Let $(S, V\setminus S)$ be any cut. Consider all edges that cross the cut. Let $e^*$ be a lightest edge among them (minimum weight). Then:

Cut property: The edge $e^*$ is safe: there exists an MST that contains $e^*$.

If the lightest crossing edge is unique, then it belongs to every MST.

Seeing the cut property (diagram)

Below, $S$ is the left group and $V\setminus S$ is the right group. The cut-crossing edges are those that go between the groups.

<svg width="640" height="220" viewBox="0 0 640 220" xmlns="http://www.w3.org/2000/svg">
  <style>
    .v { fill:#fff; stroke:#111; stroke-width:2; }
    .lbl { font: 14px sans-serif; fill:#111; }
    .cut { stroke:#888; stroke-width:2; stroke-dasharray:6 6; }
    .e { stroke:#999; stroke-width:2; }
    .elight { stroke:#0b6; stroke-width:5; }
    .w { font: 13px sans-serif; fill:#333; }
    .region { fill:#f4f8ff; stroke:#c7d6ff; stroke-width:2; }
  </style>

  <!-- regions -->
  <rect x="20" y="20" width="270" height="180" rx="14" class="region"/>
  <rect x="350" y="20" width="270" height="180" rx="14" class="region"/>
  <text x="35" y="45" class="lbl">S</text>
  <text x="365" y="45" class="lbl">V \ S</text>

  <!-- cut line -->
  <line x1="320" y1="10" x2="320" y2="210" class="cut"/>

  <!-- vertices left -->
  <circle cx="90" cy="80" r="16" class="v"/><text x="85" y="85" class="lbl">A</text>
  <circle cx="200" cy="140" r="16" class="v"/><text x="195" y="145" class="lbl">B</text>

  <!-- vertices right -->
  <circle cx="430" cy="80" r="16" class="v"/><text x="425" y="85" class="lbl">C</text>
  <circle cx="540" cy="140" r="16" class="v"/><text x="535" y="145" class="lbl">D</text>

  <!-- crossing edges -->
  <line x1="90" y1="80" x2="430" y2="80" class="e"/>
  <text x="255" y="70" class="w">w=5</text>

  <line x1="200" y1="140" x2="540" y2="140" class="e"/>
  <text x="360" y="132" class="w">w=4</text>

  <line x1="200" y1="140" x2="430" y2="80" class="elight"/>
  <text x="305" y="110" class="w" fill="#0b6">w=2 (lightest)</text>

</svg>

The cut property says: the green edge of weight 2 (the lightest crossing edge) can be included in some MST safely.

Why the cut property is true (proof sketch with breathing room)

We’ll use an “exchange argument.”

1. 1)Consider any MST $T$.
2. 2)If $T$ already contains $e^*$, we’re done.
3. 3)If not, add $e^*$ to $T$. This creates exactly one cycle (trees + 1 edge → one cycle).
4. 4)That cycle must cross the cut at least twice (to go from $S$ to $V\setminus S$ and back), so there exists some other edge $f$ on the cycle that also crosses the cut.
5. 5)Since $e^*$ is the lightest edge crossing the cut, $w(e^*) \le w(f)$.
6. 6)Remove $f$ from the cycle. The result is still connected (cycle removal keeps connectivity) and has $n-1$ edges, so it’s a spanning tree.
7. 7)The new tree has weight no greater than $T$, so it’s also an MST and contains $e^*$.

The key move is: swap in a light edge and swap out a heavier-or-equal one without breaking spanning-tree structure.

How algorithms use the cut property

• •Kruskal’s algorithm implicitly considers cuts induced by components in a forest.
• •Prim’s algorithm explicitly considers the cut $(S, V\setminus S)$ where $S$ is the set of vertices already in the growing tree.

In both cases, they repeatedly choose a lightest edge crossing a relevant cut.

Motivation: preventing cycles early vs proving an edge is useless

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

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

This becomes especially helpful for understanding Kruskal (where we sort edges and try them in order) and for reasoning about correctness.

The Cycle Property (statement)

Consider any cycle $C$ in the graph. Let $e_{max}$ be an edge on that cycle with maximum weight (a heaviest edge).

Cycle property: There exists an MST that does not contain $e_{max}$. In particular, if $e_{max}$ is uniquely the heaviest on the cycle, it is in no MST.

Intuition: within a cycle, you already have a redundant route. If one edge is the most expensive, it’s the best candidate to remove.

Seeing the cycle property (diagram)

Here’s a 4-cycle. The heaviest edge (weight 9) is highlighted in red; the cycle property says it cannot appear in an MST if it’s uniquely heaviest.

<svg width="640" height="240" viewBox="0 0 640 240" xmlns="http://www.w3.org/2000/svg">
  <style>
    .v { fill:#fff; stroke:#111; stroke-width:2; }
    .lbl { font: 14px sans-serif; fill:#111; }
    .e { stroke:#777; stroke-width:3; }
    .heavy { stroke:#c00; stroke-width:6; }
    .w { font: 13px sans-serif; fill:#333; }
  </style>

  <!-- vertices -->
  <circle cx="180" cy="70" r="16" class="v"/><text x="175" y="75" class="lbl">A</text>
  <circle cx="460" cy="70" r="16" class="v"/><text x="455" y="75" class="lbl">B</text>
  <circle cx="460" cy="170" r="16" class="v"/><text x="455" y="175" class="lbl">C</text>
  <circle cx="180" cy="170" r="16" class="v"/><text x="175" y="175" class="lbl">D</text>

  <!-- edges -->
  <line x1="180" y1="70" x2="460" y2="70" class="e"/>
  <text x="310" y="58" class="w">w=3</text>

  <line x1="460" y1="70" x2="460" y2="170" class="e"/>
  <text x="472" y="125" class="w">w=4</text>

  <line x1="460" y1="170" x2="180" y2="170" class="e"/>
  <text x="310" y="190" class="w">w=2</text>

  <line x1="180" y1="170" x2="180" y2="70" class="heavy"/>
  <text x="110" y="125" class="w" fill="#c00">w=9 (heaviest)</text>

</svg>

Why the cycle property is true (exchange argument)

Let $T$ be an MST. Suppose (for contradiction, or to build an alternative MST) that $T$ contains $e_{max}$.

• •Remove $e_{max}$ from $T$. The tree splits into two components, say $S$ and $V\setminus S$.
• •In the original cycle $C$, there is another path connecting those components (because the rest of the cycle still connects the endpoints).
• •Therefore, there exists some other edge $f$ on the cycle that crosses the cut $(S, V\setminus S)$.
• •Since $e_{max}$ is a heaviest edge on the cycle, $w(f) \le w(e_{max})$.
• •Add $f$ to reconnect the components, forming a spanning tree with weight no larger.

So we can always replace the heavy cycle edge with a no-heavier alternative.

How this connects to Kruskal

Kruskal adds edges in increasing weight order, skipping any edge that would make a cycle.

When an edge would complete a cycle, it’s necessarily not needed; and if it’s among the heavier edges on that cycle, skipping it is consistent with the cycle property.

Cut vs cycle: when to use which

• •Use cut property to justify adding an edge.
• •Use cycle property to justify excluding an edge.

Both are two sides of the same “exchange” idea: MSTs are flexible enough that local replacements preserve optimality.

Before algorithms: what greedy growth looks like

An MST has $n-1$ edges. A natural greedy plan is:

• •Start with no edges.
• •Repeatedly add a cheap edge that doesn’t break the “tree-ness.”

But there are two distinct ways to organize this growth:

1. 1)Kruskal: grow many small trees (a forest) and merge them.
2. 2)Prim: grow one tree outward from a starting vertex.

Both are correct because each step corresponds to choosing a lightest edge across some cut.

Kruskal’s algorithm

Idea

Sort all edges by weight. Scan from lightest to heaviest; add an edge if it connects two different components (i.e., doesn’t form a cycle).

Data structure: Disjoint Set Union (Union-Find)

We need to quickly answer:

• •Are $u$ and $v$ already connected by chosen edges? (Find)
• •If not, merge their components. (Union)

With path compression + union by rank/size, each operation is effectively constant amortized time.

Pseudocode

1. 1)Sort edges $E$ by increasing $w(e)$
2. 2)Initialize DSU with each vertex alone
3. 3)For each edge $(u,v)$ in sorted order:

• •If Find(u) ≠ Find(v):
• •Add edge to MST
• •Union(u, v)

4. 4)Stop when MST has $|V|-1$ edges

Correctness intuition

At any moment, Kruskal’s chosen edges form a forest. The components define a cut: pick any component as $S$, and consider edges leaving it. The next chosen edge is the lightest edge that connects two components (a lightest edge across some cut), so by the cut property it’s safe.

Complexity

• •Sorting edges: $O(|E|\log|E|)$
• •DSU operations: $O(|E|\,\alpha(|V|))$ (inverse Ackermann, tiny)

So overall: $O(|E|\log|E|)$.

When Kruskal is a good fit

• •Sparse graphs (few edges): sorting is manageable.
• •When you already have edges in sorted order (or nearly so).
• •When you want the MST but don’t care about a starting vertex.

Prim’s algorithm

Idea

Start from any vertex. Maintain a set $S$ of vertices already in the tree. Repeatedly add the lightest edge that goes from $S$ to $V\setminus S$.

This is “like Dijkstra,” but the key is: Prim uses edge weights directly to cross the boundary, not accumulated path distances.

Data structure: Priority queue over boundary edges (or keys)

Typical implementation tracks for each vertex $v \notin S$ the cheapest edge connecting it to $S$ (a key), and updates keys as $S$ grows.

Pseudocode (key-based)

1. 1)Pick a start vertex $s$
2. 2)Set key[s] = 0; key[others] = +∞
3. 3)Use a min-priority queue keyed by key[v]
4. 4)While queue not empty:

• •Extract vertex $u$ with minimum key
• •Add $u$ to $S$
• •For each edge $(u, v)$ with $v \notin S$:
• •If $w(u,v) < key[v]$:
• •key[v] = w(u,v)
• •parent[v] = u
• •Decrease-key in the priority queue

5. 5)The edges (parent[v], v) form the MST

Correctness intuition

At each step, the algorithm considers the cut $(S, V\setminus S)$ and picks the lightest edge leaving $S$ (via the minimum key). By the cut property, that edge is safe.

Complexity

• •With binary heap: $O(|E|\log|V|)$
• •With Fibonacci heap: $O(|E| + |V|\log|V|)$ (mostly theoretical)

When Prim is a good fit

• •Dense graphs (many edges): $|E|\log|V|$ can beat sorting all edges.
• •When you want a single connected growth from a start (e.g., incremental visualization, interactive building).

Kruskal vs Prim (comparison)

A note on disconnected graphs: minimum spanning forest

If $G$ is not connected, an MST doesn’t exist (can’t span all vertices). But both ideas extend:

• •Kruskal naturally returns a minimum spanning forest (one MST per component).
• •Prim can do the same by running it from each unvisited vertex.

Important nuance: undirected graphs

Classical MST is defined for undirected graphs. If edges are directed, the analogous structure is a minimum spanning arborescence (Edmonds’ algorithm), which is a different topic.

Why MSTs matter beyond “connect things cheaply”

MSTs are a core pattern: global optimization made greedy through structural properties (cuts/cycles). Once you internalize that, you’ll recognize similar proof techniques elsewhere.

Common applications

1) Network design and infrastructure

• •Laying fiber between data centers
• •Electrical grid planning (simplified)
• •Road/path planning in terrains (approximate)

MST gives a baseline “no redundancy” network. Real systems add redundancy later, but MST is often the starting scaffold.

2) Clustering (single-linkage)

Given points and pairwise distances, compute the MST of the complete graph. If you delete the $k-1$ largest edges in the MST, you get $k$ connected components—this is exactly single-linkage hierarchical clustering.

3) Approximation and subroutines

MSTs appear inside larger algorithms:

• •As part of approximation schemes (e.g., metric TSP has MST-based lower bounds).
• •In image segmentation / region merging (graph-based methods often rely on MST-like structures).

Interpreting MST edges as “bottleneck” structure

Even when you don’t care about total weight, MST has a useful minimax flavor:

• •Any MST is a minimum bottleneck spanning tree: it minimizes the maximum edge weight in the tree.

This isn’t the same objective as MST, but MST ends up optimal for it too.

How cut/cycle properties train your proof skills

These properties are classic examples of:

• •Exchange arguments (swap edges without hurting feasibility)
• •Greedy-choice property (a local step can be part of an optimum)

If you later study matroids, MST becomes a flagship example: the set of acyclic edge sets forms a matroid (graphic matroid), and greedy works.

Practical implementation tips (what you’d do in code)

• •Use Kruskal when you already have edges listed and can sort them.
• •Use Prim when you have adjacency lists and want to expand from a start, especially if graph is dense.
• •Be explicit about:
• •whether vertices are 0..n-1
• •whether edges are undirected (store both adjacency directions)
• •handling equal weights (ties don’t break correctness)

A quick mental checklist

When you see an MST problem, ask:

1. 1)Is the graph undirected and connected?
2. 2)Do I need the MST itself or just the weight?
3. 3)Is the graph sparse or dense?
4. 4)Which proof tool is relevant right now: a cut or a cycle?

That last question is the “transferable skill”: reasoning locally about global optimality.