Spanning Tree — Definition, Formula & Examples

A spanning tree is a subgraph of a connected graph that includes every vertex but uses the fewest possible edges — just enough to keep everything connected without forming any cycles.

Given a connected graph $G = (V, E)$ , a spanning tree $T = (V, E')$ is a subgraph of $G$ such that $E' \subseteq E$ , $T$ is connected, $T$ is acyclic, and $V(T) = V(G)$ . A spanning tree of a graph with $n$ vertices always has exactly $n - 1$ edges.

Key Formula

|E(T)| = |V| - 1

Where:

$|E(T)|$ = Number of edges in the spanning tree
$|V|$ = Number of vertices in the graph

How It Works

To find a spanning tree, start with a connected graph and remove edges that create cycles until no cycles remain, while keeping the graph connected. Alternatively, you can build one from scratch by adding edges one at a time, skipping any edge that would close a cycle. Two classic algorithms — Kruskal's and Prim's — find minimum spanning trees in weighted graphs by greedily selecting edges of least cost. Every connected graph has at least one spanning tree, and most have many.

Worked Example

Problem: Find a spanning tree of the complete graph

K_4

on vertices

\{A, B, C, D\}

Step 1: The complete graph

K_4

has 4 vertices and 6 edges (every pair connected). A spanning tree needs

n - 1 = 3

edges.

|E(T)| = 4 - 1 = 3

Step 2: Pick edges that connect all four vertices without forming a cycle. Start with edge

AB

, then add

BC

, then add

CD

. All four vertices are now connected and no cycle exists.

E(T) = \{AB,\, BC,\, CD\}

Step 3: Verify: the subgraph has 4 vertices, 3 edges, is connected (you can reach any vertex from any other), and contains no cycles. This is a valid spanning tree.

Answer: One spanning tree of

K_4

is the path

A - B - C - D

with edge set

\{AB, BC, CD\}

. Other spanning trees exist — for instance,

\{AB, AC, AD\}

forms a star centered at

A

Why It Matters

Spanning trees are foundational in network design — for example, finding the cheapest way to wire a set of buildings together. Minimum spanning tree algorithms appear in computer science courses, data clustering, and circuit design. Kirchhoff's matrix tree theorem counts spanning trees and connects graph theory to linear algebra.

Common Mistakes

Mistake: Confusing a spanning tree with any tree subgraph of a graph.

Correction: A spanning tree must include all vertices of the original graph. A tree subgraph that omits even one vertex is not a spanning tree.