Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 36 · Trees and Spanning Trees

Prüfer Codes and Cayley's Formula

Encode every labeled tree as a short Prüfer sequence and decode it back, then use the bijection to prove Cayley's formula n^(n-2) for counting labeled trees, verified in Python.

How many different trees can you build on the vertices 1, 2, ..., n if vertices are labeled (so a tree with 1 in the middle differs from one with 2 in the middle)? For n = 3 there are 3 trees (choose which vertex is the middle of the path). For n = 4 there are 16. For n = 5 there are 125. The pattern is Cayley's formula:

The number of labeled trees on n vertices is n^(n-2).

The most elegant proof builds a one-to-one correspondence between labeled trees and sequences of n - 2 numbers, each from 1..n. There are exactly n^(n-2) such sequences. The correspondence is the Prüfer code, invented by Heinz Prüfer in 1918.

Encoding a tree

Given a labeled tree on vertices 1..n with n ≥ 2, repeat n - 2 times:

  1. Find the leaf with the smallest label.
  2. Write down the label of its neighbor.
  3. Delete the leaf.

The n - 2 numbers written down are the Prüfer sequence. (Two vertices remain at the end; they are joined by the last edge and need no record.)

graph TD
  1 --- 4
  2 --- 4
  3 --- 5
  4 --- 5
  5 --- 6

Smallest leaf is 1, neighbor 4. Then 2, neighbor 4. Then 3, neighbor 5. Then 4, neighbor 5. The code is (4, 4, 5, 5).

Python Tree to Prüfer sequence

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A min-heap of leaves makes the whole encoding O(n log n).

Decoding a sequence

The code tells you everything. A vertex appearing k times in the sequence has degree k + 1 in the tree (each appearance is one removed neighbor, plus the edge that remains). Vertices that never appear are leaves. To rebuild:

  1. Set degree[v] = 1 + (number of times v appears).
  2. For each number x in the sequence, take the smallest vertex with current degree 1, connect it to x, and decrease both degrees.
  3. Finally connect the two remaining vertices of degree 1.
Python Prüfer sequence to tree

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Decoding gives back exactly the five edges we started with, in a different order. Because encode and decode undo each other, no two trees share a code and every sequence is a code of some tree: a bijection.

Verifying Cayley's formula

For small n we can enumerate all trees through every sequence, and also check a different way: count spanning trees of the complete graph by brute force.

Python Counting labeled trees

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A consequence: degrees

Since a vertex of degree d appears d - 1 times in the sequence, you can count trees by degree pattern. For example, the number of labeled trees on n vertices in which vertex 1 has degree d is C(n-2, d-1) · (n-1)^(n-1-d). For n = 5 and vertex 1 a leaf (d = 1) this gives 1 · 4^3 = 64. Prüfer codes also give a simple way to generate a uniformly random labeled tree: draw n - 2 random labels and decode.

Python Random tree and the star

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The star K_{1,n-1} has the code (c, c, ..., c) for its center c, and the path 1-2-...-n has code (2, 3, ..., n-1).

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many labeled trees exist on 6 vertices?

    Cayley's formula gives n^(n-2) = 6^4 = 1296.
  2. 2. How long is the Prüfer sequence of a labeled tree with n vertices?

    You remove n - 2 leaves and record one neighbor each time; the last two vertices need no record.
  3. 3. A vertex appears 4 times in a Prüfer sequence. What is its degree in the tree?

    Degree = 1 + number of appearances = 5.
  4. 4. Which vertices never appear in a Prüfer sequence?

    A vertex is recorded only as the neighbor of a removed leaf, so a leaf of the original tree (degree 1, appearing 0 times) never shows up.

Summary

  • Cayley's formula: there are n^(n-2) labeled trees on n vertices.
  • The Prüfer code repeatedly removes the smallest leaf and records its neighbor.
  • A vertex of degree d appears d - 1 times; leaves never appear.
  • Encoding and decoding are inverse, which proves the formula by a bijection.
  • Random codes generate uniformly random labeled trees.

Next: The Matrix-Tree Theorem