What is a tree?
In Unit 2 we met cycles: routes that loop back to where they started. Cycles give a network extra routes, which is good for resilience but wasteful if all you want is to connect things. A tree is what you get when you connect everything with no waste at all.
Definition
A tree is a graph that is connected and has no cycles. A graph with no cycles that may be in several pieces is called a forest: each piece is a tree.
Treea path
Treea star
Treebranching
Treea "caterpillar"
Not a treeit has cycles
Not a treetwo pieces: a forest
Trees are everywhere once you look:
- Family trees (going back from one person to their ancestors, assuming no cousin marriages).
- Folders on a computer: each folder sits inside exactly one parent folder.
- Knockout tournaments: the bracket that leads from all the teams to one champion.
- River systems: streams join into rivers that flow to the sea.
- Molecules: many chemical molecules, like the alkanes (methane, propane, butane…), have bond graphs that are trees.
Leaves
Recall from Unit 1 that a leaf is a vertex of degree 1. Leaves are the tips of a tree's branches, and every tree has some.
Theorem
Every tree with at least 2 vertices has at least 2 leaves.
Why: Pick the longest path in the tree and look at one of its ends, say x. x is joined to the next vertex along the path. Could x have another neighbour y? If y were on the path, the edge x–y would close a cycle, which trees don't have. If y were off the path, we could extend the path to y, making it longer, which contradicts "longest". So x has exactly one neighbour: it's a leaf. The same goes for the other end, so there are at least two leaves.
The path Pn shows that 2 leaves is the minimum: only its two ends are leaves. The star shows a tree can have many: every vertex except the centre is a leaf.
Why n vertices means n − 1 edges
Here is the most important fact about trees:
The proof uses leaves. Removing a leaf from a tree removes exactly one vertex and one edge, and what's left is still a tree: still connected (nothing passed through the leaf) and still free of cycles. So keep plucking leaves. The difference "vertices minus edges" never changes. At the very end you're left with a single vertex and 0 edges, where the difference is 1. So it was 1 all along.
Swipe or scroll sideways to step through.
7 vertices, 6 edges
Leaf a (amber) has degree 1. Remove it and its edge: one vertex and one edge disappear together.
6 vertices, 5 edges
Leaf c (amber) has degree 1. Remove it and its edge: one vertex and one edge disappear together.
5 vertices, 4 edges
Leaf f (amber) has degree 1. Remove it and its edge: one vertex and one edge disappear together.
4 vertices, 3 edges
Leaf g (amber) has degree 1. Remove it and its edge: one vertex and one edge disappear together.
3 vertices, 2 edges
Keep going until one edge remains, joining two vertices. Each step removed one vertex and one edge, so edges = vertices − 1 all along.
Example: a knockout tournament
64 players enter a knockout tennis tournament. How many matches are played? You could add up the rounds: 32 + 16 + 8 + 4 + 2 + 1 = 63. Or notice that every match knocks out exactly one player, and 63 players must be knocked out to leave one champion. Either way, 63. The bracket is a tree, and the counting is the "remove a leaf" argument in disguise.
Example: molecules that are trees
An alkane molecule has n carbon atoms and 2n + 2 hydrogen atoms (methane is CH4, propane is C3H8). Each carbon makes 4 bonds and each hydrogen makes 1. Using the handshake lemma, the number of bonds is (4n + 2n + 2) ÷ 2 = 3n + 1. The number of atoms is 3n + 2. Bonds = atoms − 1, and the molecule is connected, so its bond graph is a tree. In the 1870s, the mathematician Arthur Cayley counted trees partly to count possible molecules like these.
For a forest the count adjusts neatly. Each piece with k vertices has k − 1 edges, so a forest with n vertices and c trees has n − c edges.
Try it.
- A tree has 20 edges. How many vertices does it have?
- A forest has 30 vertices and 26 edges. How many trees is it made of?
- A tree has 4 vertices of degree 3, and every other vertex is a leaf. How many leaves are there?
Show answers
- 21 vertices: one more than the number of edges.
- 30 − 26 = 4 trees.
- Say there are L leaves. Then there are 4 + L vertices, so 3 + L edges. By the handshake lemma, the degrees add to twice the edges: 4 × 3 + L = 2(3 + L). That gives 12 + L = 6 + 2L, so L = 6 leaves.
Six ways to say "tree"
Trees are so tightly constrained that many different-sounding descriptions turn out to mean exactly the same thing. For a graph G with n vertices, these statements are all equivalent. If one is true, they all are.
- G is connected and has no cycles.
- G is connected and has n − 1 edges.
- G has no cycles and has n − 1 edges.
- Between any two vertices of G there is exactly one path.
- G is connected, but removing any edge disconnects it. Every edge is a bridge.
- G has no cycles, but adding any new edge creates exactly one cycle.
Statements 5 and 6 say a tree sits on a knife edge. It's minimally connected: take any edge away and it falls apart. And it's maximally acyclic: put any edge in and a cycle appears. Statement 4 explains why trees are perfect for things like folder systems: there's exactly one way to get from any folder to any other, so every file has one unambiguous address.
Watch out
"n − 1 edges" alone isn't enough. Two separate pieces, a triangle (3 vertices, 3 edges) and a single edge (2 vertices, 1 edge), have 5 vertices and 4 edges but are not a tree. You need the edge count plus either connectedness or no cycles.
Rooted trees
Often one vertex of a tree is special: the top folder, the oldest ancestor, the final match. Choosing such a vertex as the root gives every edge a natural direction, away from the root, and lets us borrow family words.
| Word | Meaning | In the folder tree |
|---|---|---|
| Root | The chosen top vertex | Home |
| Parent / child | Neighbours one level apart; the parent is nearer the root | Docs is the parent of cv and tax |
| Siblings | Vertices with the same parent | 2024 and 2025 |
| Ancestors / descendants | Everything on the path up to the root / everything below | Home and Music are ancestors of jazz |
| Depth | Distance from the root | tax has depth 2 |
| Height | The largest depth in the tree | 2 |
Every vertex except the root has exactly one parent. That's another way to see the n − 1 edge count: each non-root vertex owns the one edge leading up to its parent.
Example: binary trees and guessing games
A binary tree is a rooted tree where every vertex has at most two children. Play "I'm thinking of a number from 1 to 1000; you may ask yes/no questions". Each question splits the possibilities in two, so your strategy is a binary tree with the answers at its leaves. A binary tree of height h has at most 2h leaves, and 210 = 1024, so 10 well-chosen questions are always enough. Computers search sorted data in exactly this way.
Spanning trees
Suppose a connected graph has more edges than it needs: some cycles, some redundancy. Can we throw edges away until what's left is a tree that still reaches every vertex? Yes, always.
Definition
A spanning tree of a connected graph G is a subgraph that includes every vertex of G and is a tree.
Every connected graph has one. While the graph still has a cycle, delete one edge of that cycle. The graph stays connected, because the rest of the cycle still links the edge's two ends. When no cycles remain, you have a connected, acyclic graph on all the vertices: a spanning tree. Since it has n − 1 edges, you always delete exactly E − (n − 1) edges, however you go about it.
Example: stopping messages from looping forever
Office computer networks are often wired with redundant cables, so there are cycles. If a switch forwards a message along every cable, copies of it can circle round a cycle forever and jam the network. The standard fix, the Spanning Tree Protocol, has the switches agree on a spanning tree and only forward along its edges. The spare cables stay unused until something breaks, and then a new spanning tree is chosen.
Counting trees: Cayley's formula
How many different spanning trees does a graph have? For the complete graph K4 you can list them all. There are 16:
Arthur Cayley found the general pattern in 1889. The number of spanning trees of the complete graph Kn, which is the same as the number of different trees you can build on n labelled vertices, is:
| Vertices n | 2 | 3 | 4 | 5 | 6 | 10 |
|---|---|---|---|---|---|---|
| Labelled trees | 1 | 3 | 16 | 125 | 1,296 | 100,000,000 |
The numbers explode. With only 10 towns there are already a hundred million ways to connect them with a tree network. That's exactly why the next section matters: you can't just try them all to find the cheapest.
The cheapest network
A council wants to connect six villages to the internet with fibre cable. Some pairs of villages can be joined; each possible link has a cost. Every village must be connected, directly or indirectly, and the total cost should be as small as possible.
The cheapest solution never contains a cycle: you could delete the most expensive edge of the cycle and stay connected for less. So the answer is a spanning tree, the one with the smallest total weight. It's called a minimum spanning tree (MST).
Kruskal's algorithm (1956)
Joseph Kruskal's idea is almost too simple to work:
- Sort all the edges from cheapest to most expensive.
- Go through them in order. Add each edge unless it would create a cycle with the edges already chosen.
- Stop when you have n − 1 edges.
Swipe or scroll sideways to step through.
Start
Sort the edges from cheapest to dearest: 1, 2, 3, 4, 5, 6, 7, 8, 9. No cables are laid yet.
Take C–F (1)
The cheapest edge. It can't create a cycle, so lay it.
Take A–D (2)
Next cheapest. Still no cycle. Lay it.
Take B–E (3)
No cycle. Lay it. We now have three separate pieces: C–F, A–D and B–E.
Take A–B (4)
It joins the piece A–D to the piece B–E. Lay it.
Skip B–D (5)
B and D are already connected (B–A–D). Adding B–D would make a cycle, so skip it. D–E (6) is skipped for the same reason.
Take C–E (7)
It joins the last two pieces. Five edges for six vertices: the tree is complete. Total cost 1 + 2 + 3 + 4 + 7 = 17.
chosenbeing considered
It's called a greedy algorithm because at every step it grabs the cheapest thing available without planning ahead. Greedy strategies usually fail on hard problems, but here it's guaranteed to find the best possible tree. Roughly why: for any way of splitting the villages into two groups, the cheapest edge crossing between the groups must belong to some minimum spanning tree. If an MST didn't use that edge, swapping it in for a dearer crossing edge would make the tree cheaper. Every edge Kruskal picks is the cheapest crossing edge for some such split.
Prim's algorithm (1957)
Robert Prim's version grows a single tree outwards from a starting village, always adding the cheapest edge that connects the tree to a new vertex. Starting from A in the same graph:
| Step | Tree so far | Cheapest edge leaving the tree | Add |
|---|---|---|---|
| 1 | A | A–D (2), A–B (4) | A–D |
| 2 | A, D | A–B (4), B–D (5), D–E (6) | A–B |
| 3 | A, B, D | B–E (3), D–E (6), B–C (8) | B–E |
| 4 | A, B, D, E | C–E (7), B–C (8), E–F (9) | C–E |
| 5 | A, B, C, D, E | C–F (1), E–F (9) | C–F |
Same five edges, same total of 17. When all the edge weights are different, the minimum spanning tree is unique, so any correct method must find this exact tree.
Try it. The cable company finds that the C–E link (7) is impossible to build. What is the cheapest network now?
Show answer
Run Kruskal again without C–E. The first four choices are the same (C–F, A–D, B–E, A–B, total 10), B–D and D–E are still skipped, and the next useful edge is B–C (8), which joins the C–F piece to the rest. The new total is 10 + 8 = 18.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. Can a tree have 8 vertices and 8 edges?
Show answer
No. A tree with 8 vertices has exactly 7 edges. A connected graph with 8 vertices and 8 edges must contain exactly one cycle.
2. A connected graph has 12 vertices and 20 edges. How many edges must be removed to leave a spanning tree?
Show answer
A spanning tree has 11 edges, so remove 20 − 11 = 9 edges.
3. Draw all the different shapes of tree with 5 vertices (ignore labels).
Show answer
There are 3 shapes: the path (degrees 2, 2, 2, 1, 1), the star (one vertex of degree 4 and four leaves), and a "fork" with one vertex of degree 3 (a path of three vertices with two extra leaves hanging off one end).
4. A knockout chess tournament has 100 players. Byes are allowed when the numbers don't work out evenly. How many games are played?
Show answer
Every game eliminates exactly one player, and 99 must be eliminated. So 99 games, however the byes are arranged.
5. How many labelled trees are there on 7 vertices?
Show answer
By Cayley's formula, 75 = 16,807.
6. True or false: the most expensive edge in a graph is never in a minimum spanning tree.
Show answer
False. If the most expensive edge is a bridge, every spanning tree must use it. For example, the only cable to a remote island village must be laid, however expensive. It's true for the most expensive edge on a cycle, though: that one can always be left out.
Summary and glossary
- A tree is a connected graph with no cycles. A forest is a graph with no cycles.
- Every tree with 2 or more vertices has at least 2 leaves.
- A tree with n vertices has exactly n − 1 edges, and there's exactly one path between any two vertices.
- Choosing a root turns a tree into a hierarchy of parents and children.
- Every connected graph has a spanning tree. Kn has nn−2 of them (Cayley).
- Kruskal's and Prim's greedy algorithms find a minimum spanning tree, the cheapest way to connect everything.
- Tree
- A connected graph with no cycles.
- Forest
- A graph with no cycles; each component is a tree.
- Leaf
- A vertex of degree 1.
- Root
- A chosen vertex at the top of a rooted tree.
- Parent, child
- Adjacent vertices in a rooted tree; the parent is nearer the root.
- Depth
- A vertex's distance from the root.
- Binary tree
- A rooted tree where each vertex has at most two children.
- Spanning tree
- A tree inside a graph that includes every vertex.
- Minimum spanning tree
- A spanning tree with the smallest total edge weight.
- Greedy algorithm
- A method that always takes the best-looking option right now.