1
n − 1 edges is exactly enough
Fewer disconnects, more creates a cycle. Trees sit exactly at the boundary “Paths and Connectivity”'s edge bound identified.
Lesson · Graphs and Trees · Trees
Trees
A tree is a connected acyclic graph, and that single condition forces |E| = |V| − 1, unique paths between vertices, and every edge being a bridge. The characterisations are all equivalent.
tree = connected + acyclic
⟺ |E| = |V| − 1 and connected
⟺ exactly one path between every pair of vertices
every tree with ≥ 2 vertices has at least 2 leaves
Six ways to say the same thing
Core ideas
What this lesson establishes
Trees are the minimally connected graphs: connected, with nothing to spare.
2
Paths are unique
Two distinct paths between the same pair would form a cycle. Uniqueness is equivalent to acyclicity given connectivity.
3
Every edge is a bridge
No edge lies on a cycle, so removing any one disconnects the tree. Trees have no redundancy at all.
The material
Trees
The definition, the equivalences, and the leaf lemma.
Definition · Tree and forest
A tree is a connected acyclic graph. A forest is an acyclic graph, so its components are trees. A vertex of degree 1 is a leaf.
Theorem · Equivalent characterisations
For a graph G on n vertices, the following are equivalent: (1) G is a tree; (2) G is connected with n − 1 edges; (3) G is acyclic with n − 1 edges; (4) every pair of vertices is joined by exactly one path; (5) G is connected and every edge is a bridge; (6) G is acyclic and adding any edge creates exactly one cycle.
(1) ⟹ (4). Connectivity gives at least one path. If two distinct paths joined u and v, following one and returning by the other would produce a cycle.
(4) ⟹ (5). Unique paths mean removing any edge uv leaves no u–v route, since that edge was the only path.
(1) ⟹ (2), by induction on n. A tree on one vertex has 0 edges. For n ≥ 2, the leaf lemma below gives a leaf; removing it leaves a tree on n − 1 vertices, with n − 2 edges by hypothesis, so G has n − 1.
(2) ⟹ (1). A connected graph with a cycle can lose a cycle edge and stay connected; repeating until acyclic gives a tree, which has n − 1 edges by the previous part. Since G already had n − 1, no edge was removed and G was acyclic.
□
That proves (1) ⟺ (2) and (1) ⟹ (4) ⟹ (5); the remaining implications are of the same kind. The one the standard asks for is (3) ⟹ (1), and the tool for it is the forest edge count: an acyclic graph with c components has n − c edges, because each component is a tree and (1) ⟹ (2) applies to it.
Theorem · Leaf lemma
Every tree with at least two vertices has at least two leaves.
Take a longest path v₀ v₁ … v_k in the tree; one exists because the graph is finite, and k ≥ 1 since there are at least two vertices and the tree is connected.
Every neighbour of v₀ must lie on the path — otherwise the path could be extended, contradicting maximality — and it cannot be any vᵢ with i ≥ 2, since that would close a cycle. So v₀'s only neighbour is v₁, making it a leaf. The same argument applies at v_k.
□
The longest-path argument is a standard device and worth keeping: it produces an object that cannot be extended, and maximality is then the hypothesis that does the work.
Rooted trees
Definition · Rooted tree
A tree with one vertex designated the root. Each other vertex then has a unique parent (its neighbour toward the root), and its other neighbours are its children. The depth of a vertex is its distance from the root, and the height of the tree is the largest depth.
Rooting adds structure that the underlying tree does not have: "is an ancestor of" — the parent relation closed under transitivity — is a partial order, and it is the material of “Partial Orders”, in Sets, Relations, and Functions, appearing as a data structure.
Theorem · Binary trees
A binary tree has at most two children per vertex. One of height h has at most 2^{h+1} − 1 vertices, so a binary tree on n vertices has height at least log₂(n+1) − 1.
That bound is why balanced search trees are the data structure they are: n items can be arranged with depth about log₂ n, and search costs one comparison per level. “Searching and Sorting” in Algorithms and Complexity makes the connection to binary search explicit.
Counting trees
Theorem · Cayley's formula
The number of distinct labelled trees on n vertices is n^{n−2}. For n = 4 that is 16; for n = 10 it is a hundred million.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Recognising a tree
Two of the three conditions imply the third.
1
Count the edges
A tree on n vertices has exactly n − 1. Any other count settles it immediately.
2
Check connectivity
One search. Connected with n − 1 edges is a tree.
3
Or check for cycles
Acyclic with n − 1 edges is also a tree. Any two of connected, acyclic and n − 1 edges imply the third.
4
Find the leaves
Degree-1 vertices. There are at least two, and induction on a tree usually proceeds by removing one.
Trees
Score 0 / 0Choose the answer you can justify.
Is it a tree?
Three graphs on 6 vertices.
A: edges 1–2, 2–3, 3–4, 4–5, 5–6 |E| = 5 = n−1
connected? yes. ⟹ TREE (a path)
leaves: 1 and 6 — exactly two, the minimum
B: edges 1–2, 1–3, 1–4, 1–5, 1–6 |E| = 5 = n−1
connected? yes. ⟹ TREE (a star)
leaves: 2,3,4,5,6 — five of them
C: edges 1–2, 2–3, 3–1, 4–5, 5–6 |E| = 5 = n−1
connected? NO — two components.
⟹ NOT a tree. It is a forest? No: 1–2–3–1 is a cycle.
Right edge count, and neither connected nor acyclic.
Graph C is the warning: n − 1 edges alone proves nothing. The count is necessary and must be paired with connectivity or acyclicity, and C has neither.
Common mistakes
1
Using the edge count alonen − 1 edges is necessary and not sufficient. It must be paired with connectivity or acyclicity.
2
Assuming a rooted tree is a different objectRooting adds a designated vertex and induces the parent relation; the underlying graph is unchanged.
3
Forgetting that a forest need not be a treeAcyclic and disconnected is a forest. Its component count is n − |E|.
Check your understanding
✓
Finish when you can prove one characterisation from another.
Prove that an acyclic graph with n − 1 edges is connected. Each of its c components is a tree, so the edge count is n − c; set that equal to n − 1. It is the direction the body did not prove, and it is four lines.
Note: Trees are everywhere in computing because they combine two properties: unique paths, so navigation is unambiguous, and logarithmic depth when balanced, so navigation is fast. File systems, parse trees, search trees and decision trees are all this object.