Mathematics.

graph structures

Spanning Trees

Graph Theory30 minDifficulty5 out of 10

You should know: trees, graph connectivity

Overview

A spanning tree of a connected graph G is a subgraph that includes every vertex of G, is itself a tree (connected, no cycles), and uses only edges already present in G. Removing any cycle-forming edge from a connected graph while keeping it connected eventually leaves a spanning tree — the minimal 'skeleton' that still touches every vertex. Most connected graphs admit many different spanning trees, and counting them exactly is a classical question: Cayley's formula gives a strikingly simple count (n^(n-2)) for the complete graph, while Kirchhoff's matrix-tree theorem gives a general recipe (a single determinant) for any connected graph. Spanning trees underlie network design (minimum-cost backbone wiring), broadcast/routing protocols, and are the discrete-math ancestor of the minimum spanning tree algorithms (Kruskal's, Prim's) used throughout computer science.

Intuition

Picture a connected graph as a city with roads (edges) between every pair of intersections (vertices) that are directly linked, some of it redundant — extra roads that create shortcuts and loops. A spanning tree is the cheapest possible road network the city planner could keep while still letting every intersection reach every other one: no cycles, no redundancy, exactly n − 1 roads for n intersections. There are usually many equally-minimal ways to do this (many different spanning trees), and Cayley's and Kirchhoff's theorems are exact recipes for how many choices the planner actually has.

Formal Definition

Definition

For a connected graph G on n vertices, a spanning tree T is a subgraph with V(T) = V(G), T connected, and T acyclic — hence T always has exactly n − 1 edges. Two counting results:

T(Kn)=n n−2T(K_n) = n^{\,n-2}
Cayley's formula: number of spanning trees of the complete graph K_n
τ(G)=det⁡(Lij)(any cofactor of the graph Laplacian L)\tau(G) = \det(L_{ij}) \quad \text{(any cofactor of the graph Laplacian } L \text{)}
Kirchhoff's matrix-tree theorem: number of spanning trees of any connected graph G

Worked Examples

  1. Apply Cayley's formula with n = 4.

    T(K4)=44−2=42T(K_4) = 4^{4-2} = 4^2

  2. Evaluate.

    42=164^2 = 16

Answer: 16 spanning trees.

Practice Problems

Difficulty 4/10

Using Cayley's formula, how many spanning trees does K5 (complete graph on 5 vertices) have?

Difficulty 3/10

How many spanning trees does a path graph P4 (vertices 1-2-3-4, no other edges) have?

Difficulty 6/10

A telecom company must connect 6 relay stations that are currently fully interconnected (every pair has a direct fiber link, i.e. K6). If they want to keep only a minimal backbone (a spanning tree) to cut costs, how many fiber links will the backbone use, and how many distinct minimal backbones are theoretically possible (ignoring cost, just counting spanning trees)?

Quiz

A spanning tree of a connected graph G on n vertices always has exactly:
Cayley's formula states that the complete graph K_n has how many spanning trees?
Kirchhoff's matrix-tree theorem computes the number of spanning trees of any connected graph as:

Summary

  • A spanning tree touches every vertex of a connected graph G using only n-1 of its edges, with no cycles.
  • Cayley's formula: the complete graph K_n has exactly n^(n-2) spanning trees (e.g. K4 has 16).
  • Kirchhoff's matrix-tree theorem generalizes this to any connected graph via a Laplacian cofactor determinant.
  • Spanning trees are the combinatorial foundation for minimum spanning tree algorithms (Kruskal's, Prim's) used in network design.

References

  1. WebsiteWikipedia — Spanning tree
  2. WebsiteWikipedia — Kirchhoff's theorem