Cayley's Formula Explained with Worked Examples

Cayley's formula: there are distinct trees on labelled vertices, equivalently the complete graph has spanning trees.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Cayley's formula (labelled trees) means

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.

What is it used for?

Cayley's formula counts all the ways to connect n labelled points into a tree.

How to use cayley's formula (labelled trees)

  1. Identify the number of labelled vertices .
  2. Compute .
  3. Check small cases by listing the trees.
  4. For spanning trees of other graphs use the matrix-tree theorem.

Graph

Labelled trees nⁿ⁻² for n = 2 to 6: 1, 3, 16, 125, 1296n = 4: 16n = 6: 129612345670200400600800100012001400Labelled trees nⁿ⁻² for n = 2 to 6: 1, 3, 16, 125, 1296ntreesGraph with x from 1 to 7 and y from 0 to 1400. Shows n^(n−2) (5); point n = 4: 16 at (4, 16); point n = 6: 1296 at (6, 1296).

The count grows faster than any exponential.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: 4 vertices

How many labelled trees are there on 4 vertices?

Worked example
Answer
1616
  1. Formula

Example 2: 5 vertices

How many labelled trees are there on 5 vertices?

Worked example
Answer
125125
  1. Formula

Example 3: 6 vertices

How many labelled trees are there on 6 vertices?

Worked example
Answer
12961296
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

n = 4

4²

16 labelled trees.

n = 5

5³

125.

n = 6

6⁴

1296.

n = 3

3¹

3.

Word problems

Cayley’s formula: there are n^(n−2) labelled trees on n vertices (proved by Prüfer sequences of length n − 2).

n = 4

Count labelled trees on 4 vertices.

  1. 4²
  2. Check: ✓16

n = 5

Count labelled trees on 5 vertices.

  1. 5³
  2. Check: ✓125

n = 6 Higher

Count labelled trees on 6 vertices.

  1. 6⁴
  2. Check: ✓1296

n = 3 Higher

Count labelled trees on 3 vertices.

  1. 3¹
  2. Check: ✓3

Common mistakes

nⁿ

wrong exponent ✗

n^(n−2) ✓

Prüfer length.

Counting unlabelled

shape count ✗

labelled count ✓

Different.

n = 1

formula gives 1 ✗

one tree ✓

1^(−1) = 1.

Edges

n edges ✗

n − 1 edges ✓

Trees.

Exam tips

  1. n^(n−2).
  2. Prüfer code.
  3. n − 1 edges.
  4. Labelled vertices.
  5. Spanning trees of Kₙ.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Trees on 7 vertices Foundation

16807

2. Trees on 8 vertices Foundation

262144

3. Prüfer length for n = 9 Foundation

7

4. Edges of a tree on 10 vertices Higher

9

5. Trees on 2 vertices Higher

1

6. Trees on 4 vertices Higher

16

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Cayley’s formula
n^(n−2).
Labelled tree
Vertices distinguished.
Prüfer sequence
Code of length n − 2.
Spanning tree
Tree covering all vertices.
Complete graph (Kₙ)
All pairs joined.
Tree
Connected, acyclic.

Frequently asked questions

What is Cayley’s formula?

Kₙ has n^(n−2) spanning trees.

How many labelled trees on 5 vertices?

125.

How is it proved?

With Prüfer sequences.

How many edges does a tree have?

n − 1.

Which page covers bipartite graphs?

bipartite graphs.

Which page covers Lagrange’s theorem?

Lagrange’s theorem.

More in Discrete maths and number theory and the formula sheets.