# Chapter 30. Spanning Trees

# Chapter 30. Spanning Trees

A spanning tree is a tree that contains every vertex of a connected graph.

It keeps the vertex set of the graph but selects only enough edges to preserve connectivity. In this sense, a spanning tree is a cycle-free skeleton of a connected graph. It removes redundancy while keeping all vertices reachable.

Spanning trees are central in graph theory because they connect trees with general connected graphs. They are also central in algorithms, where one often wants a minimal connected structure inside a larger network.

## 30.1 Definition

Let

$$
G = (V,E)
$$

be a connected undirected graph.

A spanning tree of \(G\) is a subgraph

$$
T = (V,E_T)
$$

such that

$$
E_T \subseteq E
$$

and \(T\) is a tree.

The word spanning means that \(T\) contains all vertices of \(G\). Only the edge set is reduced.

If \(G\) has \(n\) vertices, then every spanning tree of \(G\) has exactly

$$
n-1
$$

edges.

## 30.2 Example

Consider the graph

$$
V=\{1,2,3,4\}
$$

with edge set

$$
E=
\{
\{1,2\},
\{2,3\},
\{3,4\},
\{4,1\},
\{1,3\}
\}.
$$

This graph is connected and contains cycles.

One spanning tree is obtained by choosing

$$
E_T=
\{
\{1,2\},
\{2,3\},
\{3,4\}
\}.
$$

The resulting subgraph contains all four vertices and has no cycle. It is a path on four vertices, so it is a tree.

Another spanning tree is

$$
E_T=
\{
\{1,3\},
\{1,4\},
\{2,3\}
\}.
$$

A connected graph may have many different spanning trees.

## 30.3 Existence of Spanning Trees

Every finite connected graph has a spanning tree.

### Theorem 30.1

If \(G\) is a finite connected graph, then \(G\) has a spanning tree.

### Proof

If \(G\) contains no cycle, then \(G\) is already a tree. Since it is connected and contains all its vertices, it is a spanning tree of itself.

Suppose \(G\) contains a cycle. Choose one edge from the cycle and remove it. The graph remains connected, because the two endpoints of the removed edge are still connected by the rest of the cycle.

If the resulting graph still contains a cycle, repeat the process.

Since \(G\) is finite, this process must stop. The final graph is connected and acyclic. Therefore it is a tree. Since no vertices were removed, it is a spanning tree of \(G\).

## 30.4 Spanning Trees as Minimal Connected Subgraphs

A spanning tree is a minimal connected spanning subgraph.

This means that it connects all vertices, and removing any edge destroys that connectivity.

### Theorem 30.2

Let \(T\) be a spanning tree of a connected graph \(G\). Then removing any edge from \(T\) disconnects \(T\).

### Proof

Since \(T\) is a tree, every edge of \(T\) is a bridge. Removing any edge from a tree disconnects it.

Thus a spanning tree contains no unnecessary edge for connectivity.

The theorem also explains why spanning trees are used as minimal network designs. Every selected edge is needed.

## 30.5 Spanning Trees and Cycles

A spanning tree removes exactly enough edges to eliminate all cycles.

Let \(G\) be a connected graph with \(n\) vertices and \(m\) edges. A spanning tree has \(n-1\) edges. Therefore one must remove

$$
m-(n-1)
$$

edges from \(G\) to obtain a spanning tree.

The number

$$
m-n+1
$$

is called the cycle rank, cyclomatic number, or circuit rank of a connected graph.

It measures the number of independent cycles in the graph.

## 30.6 Characterization by Edge Count

A connected spanning subgraph is a spanning tree exactly when it has the smallest possible number of edges.

### Theorem 30.3

Let \(G\) be a connected graph with \(n\) vertices. If \(H\) is a connected spanning subgraph of \(G\), then

$$
|E(H)| \geq n-1.
$$

Equality holds if and only if \(H\) is a spanning tree.

### Proof

Since \(H\) is connected and has \(n\) vertices, it contains a spanning tree. Every spanning tree on \(n\) vertices has \(n-1\) edges. Therefore

$$
|E(H)| \geq n-1.
$$

If equality holds, then \(H\) has exactly \(n-1\) edges. A connected graph with \(n-1\) edges is a tree. Hence \(H\) is a spanning tree.

Conversely, if \(H\) is a spanning tree, then it has exactly \(n-1\) edges.

## 30.7 Building Spanning Trees by Search

Graph traversal algorithms naturally produce spanning trees.

### Breadth-First Search Tree

If breadth-first search starts at a vertex \(s\) in a connected graph, then each newly discovered vertex records the edge by which it was first reached.

These discovery edges form a spanning tree called a BFS tree.

A BFS tree has an additional distance property. For every vertex \(v\), the distance from \(s\) to \(v\) in the BFS tree equals the shortest-path distance from \(s\) to \(v\) in the original unweighted graph.

### Depth-First Search Tree

Depth-first search also records discovery edges. These edges form a DFS tree.

A DFS tree records the recursive exploration structure of the graph. It is useful for detecting cycles, finding articulation points, computing connected components, and constructing topological orderings in directed graphs.

Both BFS and DFS show that spanning trees are constructive objects. They can be built systematically.

## 30.8 Spanning Forests in Disconnected Graphs

A disconnected graph has no spanning tree, because no connected subgraph can contain all vertices.

Instead, one uses a spanning forest.

A spanning forest contains every vertex and includes one spanning tree for each connected component.

If a graph has connected components

$$
G_1,G_2,\ldots,G_k,
$$

then a spanning forest consists of spanning trees

$$
T_1,T_2,\ldots,T_k,
$$

where \(T_i\) spans \(G_i\).

If the graph has \(n\) vertices and \(k\) components, then every spanning forest has

$$
n-k
$$

edges.

## 30.9 Counting Spanning Trees

A connected graph may have many spanning trees.

For the complete graph \(K_n\), Cayley's formula gives the number of spanning trees:

$$
n^{n-2}.
$$

For example:

| Graph | Number of spanning trees |
|---|---:|
| \(K_2\) | \(1\) |
| \(K_3\) | \(3\) |
| \(K_4\) | \(16\) |
| \(K_5\) | \(125\) |

More generally, the number of spanning trees of a graph can be computed using the Matrix-Tree Theorem, which uses the graph Laplacian.

This connects spanning trees with linear algebra and spectral graph theory.

## 30.10 Edge Exchange Property

Spanning trees satisfy an important exchange principle.

### Theorem 30.4

Let \(T\) be a spanning tree of a connected graph \(G\), and let \(e\) be an edge of \(G\) not in \(T\). Then \(T+e\) contains exactly one cycle. If \(f\) is any edge on that cycle, then

$$
T+e-f
$$

is a spanning tree, provided \(f\) lies on the cycle.

### Proof

Since \(T\) is a tree, adding the edge \(e\) creates exactly one cycle.

If an edge \(f\) on this cycle is removed, the cycle is broken. The graph remains connected, because the endpoints formerly joined through \(f\) are still connected by the rest of the cycle.

The resulting graph is connected, spans all vertices, and has \(n-1\) edges. Therefore it is a spanning tree.

This exchange property is fundamental in the theory of graphic matroids and minimum spanning tree algorithms.

## 30.11 Minimum Spanning Trees

If the edges of \(G\) have weights, then a natural problem is to find a spanning tree of minimum total weight.

Let

$$
w:E \to \mathbb{R}
$$

assign a weight to each edge.

The weight of a spanning tree \(T\) is

$$
w(T)=\sum_{e\in E(T)}w(e).
$$

A minimum spanning tree is a spanning tree \(T\) such that

$$
w(T) \leq w(T')
$$

for every spanning tree \(T'\) of \(G\).

Minimum spanning trees are used in network design, clustering, circuit layout, approximation algorithms, and image segmentation.

The next chapter studies them in detail.

## 30.12 Applications

Spanning trees appear whenever a connected structure must be reduced to a minimal connected backbone.

| Application | Role of spanning tree |
|---|---|
| Communication network | Connect all nodes with minimal links |
| Electrical network | Analyze independent branches |
| Routing | Build loop-free forwarding structure |
| Clustering | Remove high-weight edges from an MST |
| Distributed systems | Broadcast over a tree topology |
| Graph algorithms | Organize traversal and recursion |
| Approximation algorithms | Use tree structure as a simplified model |

The main advantage is structural simplicity. A spanning tree preserves reachability but removes all cycles.

## 30.13 Summary

A spanning tree of a connected graph is a tree that contains every vertex of the graph.

Every finite connected graph has at least one spanning tree. If the graph has \(n\) vertices, each spanning tree has exactly \(n-1\) edges.

Spanning trees are minimal connected spanning subgraphs. Removing any selected edge disconnects them. Adding any unused edge creates exactly one cycle.

They form a bridge between general graphs and trees. This makes them useful both theoretically and algorithmically, especially in traversal, optimization, network design, and graph decomposition.