n = 4
4²
16 labelled trees.
Cayley's formula: there are distinct trees on labelled vertices, equivalently the complete graph has spanning trees.
This page is easier if you are comfortable with:
For there are trees (a path with any of the 3 vertices in the middle). For : (12 paths and 4 stars). For : , and for : . A tree on vertices has edges (edges in a tree), chosen from the edges of (edges in a complete graph) so that there is no cycle.
A bijective proof uses Prüfer sequences: each labelled tree corresponds to a sequence of length with entries from , and there are such sequences (the counting product rule). The formula also follows from the matrix-tree theorem, which counts spanning trees by a determinant (the matrix-tree theorem, determinants).
The count grows super-exponentially. It is used in network design (the number of possible minimal connected networks), random trees and phylogenetics. Related graph counts are the handshaking lemma and the size of a minimum spanning tree.
Cayley's formula counts all the ways to connect n labelled points into a tree.
The count grows faster than any exponential.
These examples are worked by hand, step by step, so you can compare your own working.
How many labelled trees are there on 4 vertices?
How many labelled trees are there on 5 vertices?
How many labelled trees are there on 6 vertices?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
4²
16 labelled trees.
5³
125.
6⁴
1296.
3¹
3.
Cayley’s formula: there are n^(n−2) labelled trees on n vertices (proved by Prüfer sequences of length n − 2).
Count labelled trees on 4 vertices.
Count labelled trees on 5 vertices.
Count labelled trees on 6 vertices.
Count labelled trees on 3 vertices.
wrong exponent ✗
n^(n−2) ✓
Prüfer length.
shape count ✗
labelled count ✓
Different.
formula gives 1 ✗
one tree ✓
1^(−1) = 1.
n edges ✗
n − 1 edges ✓
Trees.
Try each one on paper, then open the answer. Use the solver above to see the full working.
16807
262144
7
9
1
16
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Kₙ has n^(n−2) spanning trees.
125.
With Prüfer sequences.
n − 1.
More in Discrete maths and number theory and the formula sheets.