11.4 Spanning Trees and Minimum Spanning Trees

Sections 11.1–11.3 built graph models, identified connected components, and optimized individual routes. Real communication, road, and cable networks often contain extra edges. Those edges provide alternate routes, so cycles appear. We now ask which edges are sufficient to connect every location, and then which sufficient set has the least total cost.

The graph vocabulary is now in place. A spanning tree keeps every vertex of a connected graph while removing enough edges to leave a tree-shaped backbone.

A general connection network

A finite undirected network consists of

• a set $V$ of vertices, representing locations or objects;
• a set $E$ of undirected edges, representing allowed direct connections.

The pair is written $G=(V,E)$. This object is called a graph, but no graph theory beyond the definitions stated here is assumed.

Connectedness, paths, and cycles have the meanings established in Section 11.2. Unlike a tree, a general graph may contain cycles and may have many paths between two vertices.

For example, let

and

The four outer edges form a cycle, and $\{A,C\}$ provides an additional shortcut. The network has several ways to connect all four vertices.

Spanning trees keep every vertex and remove redundancy

A spanning tree of a connected network $G=(V,E)$ is a tree

that uses every vertex of $G$ and a subset of its edges:

The word spanning means that all original vertices remain included. We may remove edges, but we may not remove vertices or invent new edges.

Because $T$ is a tree, it must satisfy three tests:

1. every vertex of $V$ appears; 2. the selected edges connect all vertices; 3. the selected edges contain no cycle.

If $|V|=n$, every spanning tree has exactly

edges. This count is a quick check, but it is not a replacement for connectedness or acyclicity.

Why every connected network has a spanning tree

Start with all edges of a connected network. If a cycle exists, remove one edge from that cycle. The remaining cycle edges still provide an alternate path between the removed edge's endpoints, so connectedness is preserved.

Repeat this deletion while any cycle remains. The finite edge set guarantees termination. The final structure is connected and acyclic, so it is a spanning tree.

This argument is also an algorithm: cycle deletion turns a connected network into a spanning tree. Different deletion choices can produce different spanning trees.

A spanning tree is a minimal connection backbone

Once a spanning tree has been selected, every chosen edge is a bridge. Removing any one selected edge breaks the tree into two connected pieces. Conversely, every unselected network edge joins two vertices that already have a unique tree path, so adding that edge creates exactly one cycle.

These facts support two ways to build a spanning tree:

• deletion view: start connected and remove cycle edges;
• addition view: start with no edges and add edges that connect pieces without forming a cycle.

Both finish with all $n$ vertices connected by $n-1$ selected edges.

Repair a city network by activating and deactivating actual links. Live component regions show which stations remain separated, while cycle alarms identify redundant loops. The goal is not simply to minimize the edge count, but to produce a connected, acyclic backbone using every station.

Weighted networks and total cost

In a weighted network, every edge $e$ has a numerical weight $w(e)$. A weight may represent cable length, construction cost, travel time, or another quantity to minimize.

The total weight of a spanning tree $T$ is

The summation adds the weight of every selected tree edge exactly once.

A minimum spanning tree, abbreviated MST, is a spanning tree whose total weight is no greater than that of any other spanning tree of the same network.

“Minimum” refers to total weight, not number of edges. Every spanning tree already has the same number $n-1$ of edges. The problem is to choose the least expensive set among them.

An MST exists whenever the network is finite, undirected, weighted, and connected. It need not be unique. Equal edge weights can allow several different spanning trees with the same minimum total. If all edge weights are distinct, the MST is unique; distinct weights are sufficient, though not necessary, for uniqueness.

Negative weights cause no logical difficulty: an MST will prefer an inexpensive negative edge when it can be included without violating the tree structure.

Kruskal's algorithm grows a forest

A forest is an acyclic structure that may have several connected components. Each component is itself a tree.

Kruskal's algorithm starts with every vertex isolated, so the selected edges form a forest. It scans edges from smallest weight to largest:

KRUSKAL(G)
    sort all edges by nondecreasing weight
    selected = empty set
    for each edge {u,v} in that order
        if u and v are in different selected components
            add {u,v} to selected
        otherwise
            skip {u,v} because it would form a cycle
    stop after n-1 edges have been selected

The phrase nondecreasing weight means each next weight is at least the previous one. Equal-weight edges may be processed in any order.

Why is the component test the same as the cycle test? If $u$ and $v$ are already in one selected component, a path already connects them. Adding $\{u,v\}$ closes that path into a cycle. If they are in different components, no path connects them, so the new edge merges two trees and cannot create a cycle.

A small Kruskal trace

Suppose edges, already sorted, have weights

• Select $AB:1$.
• Select $BC:2$; now $A,B,C$ are connected.
• Skip $AC:3$ because it would close cycle $A-B-C-A$.
• Select $CD:4$; all four vertices are connected.

The MST weight is

The cut property explains safe greedy choices

A cut divides the vertex set into two nonempty parts, $S$ and $V\setminus S$. An edge crosses the cut when one endpoint lies in each part.

The cut property states:

> For any cut, a minimum-weight edge crossing that cut is safe for at least one MST.

Here is the exchange idea. Take an MST that does not contain a chosen light crossing edge $e$. Adding $e$ creates one cycle. That cycle must cross the cut again on some edge $f$. Because $e$ is a lightest crossing edge,

Remove $f$. The result is still a spanning tree, and its total weight has not increased. Thus some MST contains $e$.

Kruskal's next accepted edge is a lightest connection between two current components, so it is light across a cut separating those components. The cut property justifies each greedy acceptance.

Prim's algorithm grows one tree

Prim's algorithm uses the same cut property differently. Choose any start vertex and let $S$ contain the vertices already reached. Repeatedly select a minimum-weight edge crossing from $S$ to $V\setminus S$, then add the new endpoint to $S$.

PRIM(G, start)
    S = {start}
    selected = empty set
    while S does not contain every vertex
        choose a minimum-weight edge {u,v}
        with u in S and v outside S
        add {u,v} to selected
        add v to S

Kruskal grows several tree components and merges them. Prim maintains one connected tree throughout. On the same connected weighted undirected network, both return an MST, though they may return different MSTs when ties exist.

Explore a weighted island network by selecting bridges yourself. Switch between Kruskal and Prim rules, inspect the eligible frontier or component merge, and challenge a hidden optimal total. Cycle-forming and non-frontier choices remain visible so the algorithm's rejection reason is concrete.

Section checklist

• A spanning tree uses every original vertex and only original edges.
• A spanning tree is connected, acyclic, and has $n-1$ edges.
• Removing cycle edges preserves connectedness until a tree remains.
• An MST minimizes total edge weight, not edge count.
• Kruskal adds light edges that merge different components.
• Prim adds a light edge crossing from one growing tree to an unreached vertex.
• The cut property explains why each accepted light crossing edge is safe.
• Tied weights may produce multiple MSTs with the same total.

Section 11.5 changes from selecting a cheapest backbone to route coverage: it asks whether one walk can use every edge once, or visit every vertex once.