4.3Trees and spanning trees
The idea
A tree is a connected graph with no cycle. It has exactly n − 1 edges and a unique path between any two vertices. A spanning tree reaches all vertices using only edges of the graph.
Think of it like this: A tree is the thinnest way to keep everyone connected: remove any road and a town is cut off, add any road and you create a loop.
Why it exists
Counting leaves and edges in trees, and counting spanning trees (Cayley, Kirchhoff), are regular questions.
How it works
- Tree ⇔ connected with n − 1 edges ⇔ acyclic with n − 1 edges.
- Every tree with n ≥ 2 has at least 2 leaves; a forest with c components has n − c edges.
- Cayley: there are n^(n−2) labelled trees on n vertices (Prüfer codes of length n − 2).
- Kirchhoff: the number of spanning trees is any cofactor of the Laplacian D − A.
Worked example: Spanning trees of K₄
By Cayley 4² = 16. The lab, using Kirchhoff, prints the same.
Now play with it
- →Load K₅ and read 125 spanning trees.
- →Load the 7-vertex tree and read its Prüfer sequence.
Check yourself
A tree has 4 vertices of degree 3 and every other vertex is a leaf. How many leaves does it have?
Exam notes (the dense version)
A tree is a connected acyclic graph. Equivalent: connected with n−1 edges; acyclic with n−1 edges; exactly one path between any two vertices. Every tree with n ≥ 2 has at least 2 leaves. A forest with c components has n − c edges. Cayley: n^(n−2) labelled trees on n vertices (Prüfer codes). The number of spanning trees of K_n is n^(n−2); in general use Kirchhoff: any cofactor of the Laplacian D − A.
Previous year questions: Graph Theory (24)
PYQs are grouped by topic, so this is the full set for Graph Theory; try the ones that match this subtopic. Open all 24 on the topic page.