Prüfer sequences are defined only for trees with \(n>1\) vertices. For the case \(n=1\), special handling is required.

A Prüfer sequence establishes a bijection between labeled rooted trees on \(n\) vertices and sequences of length \(n-2\) drawn from \([1,n]\cap\Z\). This encoding transforms tree structures into arrays, which proves invaluable for combinatorial counting problems.

The following presents the construction of Prüfer sequences from trees, followed by the reconstruction process that demonstrates the bijection property.

Constructing the Prüfer Sequence

Each iteration finds the leaf with the smallest label, appends the label of its only neighbor to the sequence, and removes the leaf. After performing this operation \(n-2\) times, exactly two vertices connected by a single edge remain. The resulting sequence of length \(n-2\) is the Prüfer sequence.

Since vertex \(n\) never becomes a leaf during this process, we designate it as the root. This convention simplifies implementation since the unique neighbor of each leaf is its parent. By maintaining the child count for each vertex, we can efficiently identify leaves and always extract the minimum label using a priority queue.

A linear-time algorithm exists. After inserting a label, we check whether its the current minimum. If so, we consume it immediately; otherwise, we add it to the leaf set. This monotonicity property allows us to use bucket-based storage with a single pointer tracking the current minimum.

Implementation:

void prf_init() {
    for (int i = 1; i < n; i++) deg[fa[i]]++;
    for (int i = 1; i <= n; i++)
        if (!deg[i]) hav[i]++;
    int now = 1, least = 0, d;
    for (int i = 1; i <= n - 2; i++) {
        if (least) d = least, least = 0;
        else {
            while (!hav[now]) now++;
            d = now;
            hav[now]--;
        }
        prf[i] = fa[d];
        if (!--deg[fa[d]])
            if (fa[d] < now) least = fa[d];
            else hav[fa[d]]++;
    }
}

Reconstructing the Tree from a Prüfer Sequence

From the construction process, the number of occurrences of vertex \(i\) in the Prüfer sequence equals \(\deg_i - 1\). For \(x\neq n\), all children of \(x\) get removed during the process. For \(x=n\), exactly one child remains undeleted, but unlike non-root vertices, this child has no incoming edge contribution to the degree.

Knowing the degree of each vertex, we can determine the initial leaf set. To reconstruct the tree, we simulate the construction process from left to right. Each step identifies the current smallest leaf, and we know an edge exists between that leaf and the corresponding Prüfer sequence value. After \(n-2\) iterations, we have \(n-2\) edges. The remaining edge connects vertex \(n\) to whichever vertex in \([1,n)\) still lacks a parent.

The simulation process mirrors the linear construction algorithm described above, so the implementation closely resembles the encoding code.

Implementation:

void fa_init() {
    for (int i = 1; i <= n - 2; i++) deg[prf[i]]++;
    for (int i = 1; i <= n; i++)
        if (!deg[i]) hav[i]++;
    int now = 1, least = 0, d;
    for (int i = 1; i <= n - 2; i++) {
        if (least) d = least, least = 0;
        else {
            while (!hav[now]) now++;
            d = now;
            hav[now]--;
        }
        fa[d] = prf[i];
        if (!--deg[fa[d]])
            if (fa[d] < now) least = fa[d];
            else hav[fa[d]]++;
    }
    for (int i = 1; i < n; i++)
        if (!fa[i]) fa[i] = n;
}

Application: Counting Labeled Trees

An immediate consequence of the bijection is that the number of labeled trees on \(n>1\) vertices equals \(n^{n-2}\). This result can also be derived using Kirchhoff's Matrix Tree Theorem, though the algebraic proof involves more steps.

For the complete graph on \(n\) vertices, we seek to prove that the determinant of the reduced Laplacian matrix equals \(n^{n-2}\):

[\begin{vmatrix}n-1&-1&-1&\cdots&-1\-1&n-1&-1&\cdots&-1\-1&-1&n-1&\cdots&-1\\vdots&\vdots&\vdots&\ddots&-1\-1&-1&-1&-1&n-1\end{vmatrix}=n^{n-2}]

Subtract the first row from all other rows. Let \(K_x\) denote the resultign \(x\times x\) matrix:

[\begin{bmatrix}n-1&-1&-1&\cdots&-1\-n&n&-n&&n\\vdots&&&\ddots\-n&&&&n\end{bmatrix}]

We claim that \(|K_x|=(n-x)n^{x-1}\), proved by induction on \(x\).

Base case: \(|K_1|=n-1\) holds trivially.

Inductive step for \(x>1\): Expand along the second row. The \((2,1)\) cofactor is an upper triangular matrix yielding \(-n^{x-2}\). The \((2,2)\) cofactor equals \(|K_{x-1}|\). All other positions contribute zero.

Assuming the inductive hypothesis holds for \(K_{x-1}\), we compute:

[\begin{aligned}|K_x|&=(-1)^{2+1}(-n)!\left(-n^{x-2}\right)+(-1)^{2+2}n(n-x+1)n^{x-2}\&=-n^{x-1}+(n-x+1)n^{x-1}\&=(n-x)n^{x-1}\end{aligned}]

This completes the proof.