Prüfers

Prüfers refers to the Prüfer code (or Prüfer sequence), a famous construction in graph theory named after the German mathematician Heinz Prüfer. It provides a simple, bijective correspondence between labeled trees and sequences, making it a fundamental tool in combinatorics and related fields.

The code applies to labeled trees on n vertices labeled with the set {1, 2, ..., n}. The Prüfer sequence is a sequence of length n−2 whose entries are drawn from the same label set. Encoding is performed by repeatedly removing the leaf (a vertex of degree 1) with the smallest label and recording the label of its unique neighbor; this is done until only two vertices remain. The resulting sequence is the Prüfer code of the original tree. Decoding works in reverse: given a Prüfer sequence, repeatedly insert the smallest label not present in the remaining sequence and join it to the current first element of the sequence, updating the multiset as you go, until the tree is reconstructed.

A key consequence is Cayley’s formula: the number of labeled trees on n vertices is n^{n−2}. The Prüfer code thus yields a straightforward bijection between these trees and all possible sequences of length n−2 from {1,...,n}. This encoding is also useful for generating uniformly random labeled trees, studying degree distributions, and various enumeration problems in graph theory and computer science.

In addition to the original concept, Prüfer's work has influenced related encodings and generalizations in combinatorics, where similar ideas encode combinatorial structures by bijections with sequences.