A family tree, the folders on your laptop, the HTML DOM, a tournament bracket, the routing that stops network packets from looping forever: all of these are trees. Trees are the simplest connected graphs, with just enough edges to hold everything together and not one edge more. That minimality makes them easy to reason about and extremely useful.
In this chapter we define trees, prove the key facts about them (why a tree on n vertices always has n − 1 edges), learn the vocabulary of rooted and m-ary trees, count labelled trees with Cayley's formula and Prüfer codes, count spanning trees with the Matrix-Tree Theorem, and finish with minimum spanning trees (Kruskal and Prim). We use the basic terms from Graph Theory Basics (paths, cycles, connectivity) throughout.
A tree is a connected graph with no cycles. A forest is a graph with no cycles (so each of its components is a tree). A spanning tree of a connected graph G is a subgraph that is a tree and contains every vertex of G.
Every count in this chapter (spanning trees, labelled trees, MST weights) was verified by computer.
Basic Properties of Trees
Leaves
A leaf is a vertex of degree 1.
Lemma. Every tree with at least 2 vertices has at least 2 leaves.
Proof. Take a longest path P = v0 v1 … vk in the tree (k ≥ 1 because there is at least one edge). Suppose v0 had a neighbour w other than v1. If w is on P, the edge v0w closes a cycle, which is impossible in a tree. If w is not on P, then w v0 v1 … vk is a longer path, contradicting the choice of P. So deg(v0) = 1, and by the same argument deg(vk) = 1. ∎
A tree on n vertices has n − 1 edges
Theorem. Every tree with n vertices has exactly n − 1 edges.
Proof by induction on n (the technique from Mathematical Induction). For n = 1 there are 0 edges. Let T be a tree with n ≥ 2 vertices. By the lemma, T has a leaf v. Removing v and its single edge leaves a graph T − v that is still connected (no path between two other vertices can pass through a degree-1 vertex) and still has no cycles. So T − v is a tree with n − 1 vertices, and by the induction hypothesis it has n − 2 edges. Adding back v's edge gives n − 1. ∎
Applying this to each component: a forest with n vertices and c components has n − c edges.
Equivalent definitions
For a graph T with n vertices, the following statements are all equivalent. Any one of them can serve as the definition of a tree:
T is connected and has no cycles.
T is connected and has n − 1 edges.
T has no cycles and has n − 1 edges.
There is exactly one path between every pair of vertices.
T is minimally connected: connected, but removing any edge disconnects it. (Every edge is a bridge.)
T is maximally acyclic: no cycles, but adding any new edge creates exactly one cycle.
Two of the implications, to show the flavour. (1) ⇒ (4): connected gives at least one path. If there were two different paths from u to w, follow them from u until they first split, and then until they first meet again; those two pieces form a cycle. (2) ⇒ (1): if a connected graph with n − 1 edges had a cycle, we could delete cycle edges (each deletion keeps it connected) until no cycle remains, giving a tree with fewer than n − 1 edges, contradicting the theorem.
Counting leaves from degrees
Suppose a tree has ni vertices of degree i. Then n = Σ ni and, by the handshaking lemma, Σ i·ni = 2(n − 1). Subtracting 2n = Σ 2ni from both sides:
Σ (i − 2)·n_i = −2 ⟹ n_1 = 2 + Σ_{i ≥ 3} (i − 2)·n_i
Degree-2 vertices do not affect the number of leaves at all.
Worked example. A tree has 2 vertices of degree 4, 1 vertex of degree 3, 3 vertices of degree 2, and all other vertices are leaves. How many leaves? n1 = 2 + 2·(4 − 2) + 1·(3 − 2) = 2 + 4 + 1 = 7. Check: n = 2 + 1 + 3 + 7 = 13 vertices, degree sum 8 + 3 + 6 + 7 = 24 = 2 × 12 edges. ✓
Rooted Trees and m-ary Trees
Choosing one vertex as the root gives every edge a direction (away from the root) and the familiar computer-science vocabulary:
Term | Meaning |
|---|---|
Parent / child | If u is the neighbour of v on the path from v to the root, u is v's parent and v is u's child |
Ancestor / descendant | Vertices on the path from v to the root / vertices whose path to the root passes through v |
Leaf / internal vertex | No children / at least one child |
Level (depth) of v | Length of the path from the root to v (root at level 0) |
Height | Maximum level of any vertex |
Subtree at v | v together with all its descendants |
A rooted tree is m-ary if every internal vertex has at most m children, and full m-ary if every internal vertex has exactly m children. Binary means m = 2.
Formulas for full m-ary trees
Every vertex except the root is the child of exactly one internal vertex, so with i internal vertices, n = mi + 1. Combining this with n = i + l (l = number of leaves):
Given | n (total) | i (internal) | l (leaves) |
|---|---|---|---|
i | mi + 1 | i | (m − 1)i + 1 |
n | n | (n − 1)/m | ((m − 1)n + 1)/m |
l | (ml − 1)/(m − 1) | (l − 1)/(m − 1) | l |
Example. A full 3-ary tree with 10 internal vertices has n = 31 vertices and l = 21 leaves.
Example. A knockout tournament with 64 players is a full binary tree with 64 leaves, so it has (64 − 1)/(2 − 1) = 63 internal vertices: 63 matches. (Simpler reason: every match eliminates exactly one player, and 63 must be eliminated.)
Two more facts used constantly in data structures:
An m-ary tree of height h has at most mh leaves, and a binary tree of height h has at most 1 + 2 + … + 2h = 2h+1 − 1 vertices. So a binary tree with n vertices has height at least ⌈log2(n + 1)⌉ − 1.
In any binary tree, (number of leaves) = (number of vertices with 2 children) + 1.
Counting Trees
Unlabelled trees
Up to isomorphism (see Graph Representations & Isomorphism), the number of different trees on n vertices for n = 1, 2, …, 8 is 1, 1, 1, 2, 3, 6, 11, 23. For example, on 4 vertices there are just 2: the path P4 and the star K1,3. There is no simple closed formula for this sequence.
Labelled trees: Cayley's formula
Cayley's formula. The number of different trees on the labelled vertex set {1, 2, …, n} is nn − 2.
For n = 4 that is 16: the 4 labellings of the star (choose the centre) plus 4!/2 = 12 labellings of the path (a path and its reverse are the same tree). 4 + 12 = 16 ✓. Equivalently, Kn has nn − 2 spanning trees.
Prüfer codes: a bijection that proves Cayley
A Prüfer code turns a labelled tree on n ≥ 2 vertices into a sequence of length n − 2 with entries from {1, …, n}, and every such sequence comes from exactly one tree. There are nn − 2 sequences, so there are nn − 2 trees (the bijection idea from Functions).
Encode: repeat n − 2 times:
remove the leaf with the smallest label,
write down its (only) neighbour.
Decode: degree(v) = 1 + (number of times v appears in the code)
for each x in the code, in order:
let v = smallest label with degree 1
add edge v–x; delete v; degree(x) −= 1
finally join the two vertices that remain.
Worked example. Encode the tree on {1, …, 7} with edges 1–4, 2–4, 3–4, 4–5, 5–6, 6–7:
1 2 3
╲ │ ╱
4 ── 5 ── 6 ── 7
Step | Current leaves | Remove | Write |
|---|---|---|---|
1 | 1, 2, 3, 7 | 1 | 4 |
2 | 2, 3, 7 | 2 | 4 |
3 | 3, 7 | 3 | 4 |
4 | 4, 7 | 4 | 5 |
5 | 5, 7 | 5 | 6 |
Code: (4, 4, 4, 5, 6); vertices 6 and 7 remain. Notice that vertex 4 appears 3 times and has degree 4: each vertex appears (degree − 1) times, so the leaves are exactly the labels that never appear.
This gives quick answers to counting questions. Example: how many labelled trees on {1, …, n} have vertex 1 as a leaf? The code must avoid the label 1, so there are (n − 1)n − 2 such trees (64 for n = 5).
Spanning Trees
Every connected graph has a spanning tree. While the graph has a cycle, delete one edge of that cycle: the graph stays connected, and the process stops with a connected acyclic spanning subgraph. BFS and DFS also produce spanning trees directly (keep the edges used to discover new vertices).
A connected graph with n vertices and e edges must lose exactly e − n + 1 edges to become a spanning tree. This number is the cycle rank (cyclomatic number). It is closely related to McCabe's cyclomatic complexity in software engineering, which for a connected control-flow graph is e − n + 2, one more than the cycle rank.
How many spanning trees? The Matrix-Tree Theorem
The Laplacian matrix of G is L = D − A, where D is the diagonal matrix of degrees and A is the adjacency matrix.
Kirchhoff's Matrix-Tree Theorem. The number of spanning trees τ(G) equals the determinant of the matrix obtained from L by deleting any one row and the same-numbered column.
Worked example: the diamond (K4 minus one edge) with vertices 0, 1, 2, 3 and edges 01, 02, 12, 13, 23. Degrees are 2, 3, 3, 2.
┌ 2 −1 −1 0 ┐ ┌ 3 −1 −1 ┐
L = │ −1 3 −1 −1 │ delete row/col 0: │ −1 3 −1 │
│ −1 −1 3 −1 │ └ −1 −1 2 ┘
└ 0 −1 −1 2 ┘
det = 3·(3·2 − (−1)(−1)) − (−1)·((−1)·2 − (−1)(−1)) + (−1)·((−1)(−1) − 3·(−1))
= 3·5 + (−3) − 4
= 8
Cross-check by direct counting: a spanning tree picks 3 of the 5 edges, C(5, 3) = 10 ways. A 3-edge set fails only if it contains a cycle, and the only 3-edge cycles are the two triangles (the outer 4-cycle needs 4 edges). So τ = 10 − 2 = 8. ✓
Formulas to remember
Graph | Number of spanning trees | Example |
|---|---|---|
Any tree | 1 | - |
Cycle Cn | n (delete any one edge) | C6: 6 |
Complete graph Kn | nn − 2 | K5: 125 |
Complete bipartite Km,n | mn − 1·nm − 1 | K2,3: 12; K3,4: 432 |
Petersen graph | 2000 | - |
Minimum Spanning Trees
In a weighted connected graph, a minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Think of connecting villages with the least total length of cable.
Cut property. Split the vertices into two non-empty groups S and V − S. If e is the unique lightest edge with one end in each group, then every MST contains e.
Proof. Let T be a spanning tree that does not contain e. Adding e to T creates exactly one cycle (characterization 6). That cycle crosses from S to V − S along e, so it must cross back along some other edge f of T. Then T + e − f is connected with n − 1 edges, so it is a spanning tree, and since w(e) < w(f) it is strictly lighter. So T was not minimum. ∎
A matching cycle property says that the unique heaviest edge on any cycle is in no MST. It also follows that when all edge weights are distinct, the MST is unique.
Both classic algorithms are greedy, and the cut property is exactly why their greedy choices are safe:
Kruskal: sort the edges by weight; take each edge unless it would form a cycle with edges already taken (checked with a union-find structure). O(E log E).
Prim: grow a single tree from a start vertex; at each step add the lightest edge leaving the tree. O(E log V) with a binary heap.
Worked example
Vertices A–F. Edges (weight):
B–C 1, B–D 2, A–C 3, A–B 4, C–E 5, C–D 6, D–E 7, E–F 8, D–F 9
Kruskal considers | Decision |
|---|---|
B–C 1 | take |
B–D 2 | take |
A–C 3 | take |
A–B 4 | skip: A and B already connected through C |
C–E 5 | take |
C–D 6 | skip: C–B–D already exists |
D–E 7 | skip: D–B–C–E already exists |
E–F 8 | take; now 5 = n − 1 edges, stop |
MST = {B–C, B–D, A–C, C–E, E–F}, total weight 1 + 2 + 3 + 5 + 8 = 19. Prim from A adds A–C 3, C–B 1, B–D 2, C–E 5, E–F 8 (in that order) and reaches the same tree, as it must, since the weights are distinct.
Checking with Code
Prüfer encoding and decoding, the Matrix-Tree Theorem with exact fractions, and both MST algorithms, in standard Python.
from fractions import Fraction
import heapq
def prufer_encode(n, edges):
"""Pruefer sequence of a labelled tree on vertices 1..n."""
adj = {v: set() for v in range(1, n + 1)}
for a, b in edges:
adj[a].add(b)
adj[b].add(a)
seq = []
for _ in range(n - 2):
leaf = min(v for v in adj if len(adj[v]) == 1) # smallest leaf
parent = adj[leaf].pop()
seq.append(parent)
adj[parent].discard(leaf)
del adj[leaf]
return seq
def prufer_decode(seq):
n = len(seq) + 2
degree = {v: 1 for v in range(1, n + 1)}
for x in seq:
degree[x] += 1
edges = []
for x in seq:
leaf = min(v for v in degree if degree[v] == 1)
edges.append((leaf, x))
del degree[leaf]
degree[x] -= 1
u, w = [v for v in degree if degree[v] == 1]
edges.append((u, w))
return edges
def spanning_tree_count(n, edges):
"""Kirchhoff: any cofactor of the Laplacian (exact arithmetic with fractions)."""
L = [[Fraction(0)] * n for _ in range(n)]
for a, b in edges:
L[a][a] += 1; L[b][b] += 1
L[a][b] -= 1; L[b][a] -= 1
M = [row[1:] for row in L[1:]] # delete row 0 and column 0
det, m = Fraction(1), len(M)
for c in range(m): # Gaussian elimination
p = next((r for r in range(c, m) if M[r][c] != 0), None)
if p is None:
return 0
if p != c:
M[c], M[p] = M[p], M[c]
det = -det
det *= M[c][c]
for r in range(c + 1, m):
f = M[r][c] / M[c][c]
for j in range(c, m):
M[r][j] -= f * M[c][j]
return int(det)
def kruskal(vertices, weighted_edges):
parent = {v: v for v in vertices}
def find(v):
while parent[v] != v:
parent[v] = parent[parent[v]] # path halving
v = parent[v]
return v
tree = []
for w, a, b in sorted(weighted_edges):
ra, rb = find(a), find(b)
if ra != rb: # different components: no cycle
parent[ra] = rb
tree.append((a, b, w))
return tree
def prim(vertices, weighted_edges, start):
adj = {v: [] for v in vertices}
for w, a, b in weighted_edges:
adj[a].append((w, a, b))
adj[b].append((w, b, a))
seen, tree, heap = {start}, [], list(adj[start])
heapq.heapify(heap)
while heap and len(seen) < len(vertices):
w, a, b = heapq.heappop(heap)
if b not in seen:
seen.add(b)
tree.append((a, b, w))
for item in adj[b]:
heapq.heappush(heap, item)
return tree
edges7 = [(1, 4), (2, 4), (3, 4), (4, 5), (5, 6), (6, 7)]
code = prufer_encode(7, edges7)
print("Pruefer code:", code)
print("Decoded edges:", prufer_decode(code))
diamond = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
k4 = [(a, b) for a in range(4) for b in range(a + 1, 4)]
k23 = [(a, b) for a in (0, 1) for b in (2, 3, 4)]
print("Spanning trees: diamond =", spanning_tree_count(4, diamond),
" K4 =", spanning_tree_count(4, k4), " K2,3 =", spanning_tree_count(5, k23))
V = "ABCDEF"
E = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"), (6, "C", "D"),
(5, "C", "E"), (7, "D", "E"), (9, "D", "F"), (8, "E", "F")]
for name, t in (("Kruskal", kruskal(V, E)), ("Prim from A", prim(V, E, "A"))):
print(f"{name:12}", t, " total =", sum(w for _, _, w in t))
Output:
Pruefer code: [4, 4, 4, 5, 6]
Decoded edges: [(1, 4), (2, 4), (3, 4), (4, 5), (5, 6), (6, 7)]
Spanning trees: diamond = 8 K4 = 16 K2,3 = 12
Kruskal [('B', 'C', 1), ('B', 'D', 2), ('A', 'C', 3), ('C', 'E', 5), ('E', 'F', 8)] total = 19
Prim from A [('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('C', 'E', 5), ('E', 'F', 8)] total = 19
Decoding gives back exactly the original edges, which is the bijection in action. K4 gives 16 = 42, matching Cayley's formula.
Common Mistakes
"n − 1 edges, so it is a tree." Only if it is also connected (or acyclic). Two disjoint triangles plus an isolated vertex have 7 vertices and 6 edges, but together they do not form a tree.
Counting levels inconsistently. Some books put the root at level 1 and define height as the number of levels. Check the convention before using 2h+1 − 1.
Applying full m-ary formulas to trees that are not full. n = mi + 1 needs every internal vertex to have exactly m children.
Confusing labelled and unlabelled counts. There are 16 labelled trees on 4 vertices but only 2 up to isomorphism.
In Kruskal, skipping an edge just because its endpoints were seen before. The test is whether they are already in the same component, not whether they have been touched.
Assuming the MST is unique. It is unique when weights are distinct; with ties there may be several MSTs (all with the same total weight).
Practice and GATE-Style Questions
Q1. A forest has 40 vertices and 34 edges. How many trees does it contain?
A forest with c components has n − c edges: 40 − c = 34, so c = 6.
Q2. A tree has 3 vertices of degree 3, 4 vertices of degree 2, and the rest are leaves. How many vertices does it have?
Leaves: n1 = 2 + 3·(3 − 2) = 5. Total n = 3 + 4 + 5 = 12. Check: degree sum 9 + 8 + 5 = 22 = 2 × 11. ✓
Q3. How many spanning trees does K2,4 have?
mn − 1·nm − 1 with m = 2, n = 4: 23·41 = 32.
Q4. Decode the Prüfer code (3, 3, 4) into a tree on {1, …, 5}.
Degrees: 3 → 3, 4 → 2, others → 1. Step 1: smallest leaf 1, edge 1–3 (deg 3 becomes 2). Step 2: smallest leaf 2, edge 2–3 (deg 3 becomes 1). Step 3: smallest leaf is now 3, edge 3–4 (deg 4 becomes 1). Remaining: 4 and 5, edge 4–5. Tree: 1–3, 2–3, 3–4, 4–5.
Q5. A connected graph has 10 vertices and 15 edges. How many edges must be removed to obtain a spanning tree?
e − n + 1 = 15 − 10 + 1 = 6.
Q6. Interview: why does Kruskal's algorithm never create a cycle, and why is its result optimal?
It accepts an edge only when its endpoints lie in different union-find components, so the accepted edges always form a forest. Optimality: when an edge e = uv is accepted, take S = the component containing u. Every edge lighter than e was considered earlier and either accepted or rejected; either way its two ends are now in the same component, so it does not cross the cut between S and the rest. Hence e is a lightest edge crossing that cut, and the cut-property exchange argument shows it can be added without losing optimality. (With distinct weights this is exactly the cut property as stated.)
Summary
A tree is connected and acyclic; equivalently connected with n − 1 edges, or with a unique path between every pair of vertices. A forest with c components has n − c edges.
Every tree with ≥ 2 vertices has ≥ 2 leaves; n1 = 2 + Σi ≥ 3(i − 2)ni.
Full m-ary tree with i internal vertices: n = mi + 1, l = (m − 1)i + 1.
Cayley: nn − 2 labelled trees, proved by the Prüfer bijection (each vertex appears degree − 1 times).
Every connected graph has a spanning tree; count them with the Matrix-Tree Theorem (det of a Laplacian cofactor).
MST: Kruskal (sort edges, avoid cycles) and Prim (grow from a vertex) are both correct because of the cut property.
A tree is a graph with exactly enough edges to stay connected. Remove one and it falls apart; add one and a cycle appears. Almost every theorem in this chapter is a consequence of that balance.