ii. Tree Isomorphism and Prüfer Codes

Two trees are isomorphic if some bijection $\phi$ on vertices preserves adjacency: $(u,v)\in E_1⟺(\phi u,\phi v)\in E_2$. Graph isomorphism in general has no known polynomial algorithm (quasipolynomial, Babai 2016) and is not known to be in P or NP-complete; in practice tools like nauty use refinement plus backtracking. For trees specifically it drops to $O(n\log n)$: rooted trees are compared by canonical forms built bottom-up (AHU); unrooted trees are rooted at their centre(s) first. Labelled trees on $n$ vertices are in bijection with sequences of length $n-2$ (Prüfer codes), which proves Cayley’s $n^{n-2}$ and turns degree-constrained tree counting into sequence counting.

AHU canonical ids

Give every rooted subtree an integer id: a vertex’s id is determined by the sorted list of its children’s ids (looked up in a dictionary shared by all trees being compared). Two rooted trees are isomorphic iff their roots get the same id. $O(n\log n)$.

struct TreeCanon {
    map<vector<int>, int> ids;                               // shared across all trees compared
    int rooted(const vector<vector<int>>& adj, int root, vector<int>* all = nullptr) {
        int n = sz(adj); vector<int> par(n, -1), order{root}, id(n);
        for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
        for (int i = n - 1; i >= 0; i--) {
            int u = order[i]; vector<int> ch;
            for (int v : adj[u]) if (v != par[u]) ch.push_back(id[v]);
            sort(all(ch));
            auto it = ids.find(ch);
            id[u] = it != ids.end() ? it->second : ids[ch] = sz(ids);
        }
        if (all) *all = id;                                  // ids of every rooted subtree
        return id[root];
    }
    pair<int, int> unrooted(const vector<vector<int>>& adj) {   // canonical: sorted ids at the centre(s)
        auto c = treeCenters(adj);
        int a = rooted(adj, c[0]), b = sz(c) > 1 ? rooted(adj, c[1]) : a;
        return {min(a, b), max(a, b)};
    }
};

Proof: AHU ids characterise rooted isomorphism; centres for unrooted trees

By induction on height: two rooted trees are isomorphic iff there is a bijection between the children of the roots matching isomorphic child subtrees, iff the multisets of child classes are equal, iff the sorted lists of child ids are equal (ids are in bijection with classes by the inductive hypothesis), iff the roots get the same id. Unrooted: an isomorphism maps centres to centres (eccentricity is preserved), so $T_1\cong T_2$ iff $T_1$ rooted at some centre is isomorphic to $T_2$ rooted at some centre; when a tree has two centres both rootings are taken, and comparing the sorted pairs covers every case (a tree with one centre gives the pair $(a,a)$, which can only equal another one-centre pair). Time: each vertex’s children are sorted, $O(n\log n)$ in total, plus dictionary lookups whose key lengths sum to $n-1$.

Hashing with a guarantee

For one-off comparisons or many trees, hash instead: with a random $x_h$ per height $h$, set $P(\text{leaf})=1$ and $P(u)={\prod }_c(x_{h(u)}+P(c))\mathrm{mod}p$. Isomorphic rooted trees get equal values, and non-isomorphic ones collide with probability $\le n/p$; use $p=2^{61}-1$.

struct TreeHash {                                            // P(u) = prod over children (x[height(u)] + P(c)) mod 2^61-1
    static constexpr ull MOD = (1ULL << 61) - 1;
    static ull mul(ull a, ull b) { __uint128_t c = (__uint128_t)a * b; ull r = (ull)(c >> 61) + (ull)(c & MOD); return r >= MOD ? r - MOD : r; }
    vector<ull> x; mt19937_64 rng{chrono::steady_clock::now().time_since_epoch().count()};
    ull rooted(const vector<vector<int>>& adj, int root, vector<ull>* all = nullptr) {
        int n = sz(adj); vector<int> par(n, -1), order{root}, h(n); vector<ull> P(n, 1);
        for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
        for (int i = n - 1; i > 0; i--) h[par[order[i]]] = max(h[par[order[i]]], h[order[i]] + 1);
        while (sz(x) <= n) x.push_back(rng() % MOD);
        for (int i = n - 1; i >= 0; i--) {
            int u = order[i];
            for (int v : adj[u]) if (v != par[u]) { ull t = x[h[u]] + P[v]; if (t >= MOD) t -= MOD; P[u] = mul(P[u], t); }
        }
        if (all) *all = P;
        return P[root];
    }
};

Proof: the polynomial hash is exact up to Schwartz–Zippel

View $P(u)$ as a polynomial in the variables $x_0,x_1,\dots$. A child $c$ of $u$ has $h(c)<h(u)$, so $P(c)$ does not involve $x_{h(u)}$, and $P(u)$ is a monic polynomial in $x_{h(u)}$ with roots $-P(c)$ over the ring of the other variables. Polynomial rings over a field are unique factorisation domains, so $P(u)$ determines its height (the variable it is monic in; leaves are the constant 1) and the multiset $\{P(c)\}$. By induction, equal polynomials mean isomorphic rooted trees, and isomorphic trees obviously give equal polynomials. $P$ has total degree $\le n$, so two different polynomials agree at a uniformly random point modulo the prime $p$ with probability $\le n/p$ (Schwartz–Zippel); with $p=2^{61}-1$ and up to $10^6$ comparisons the failure probability is about $10^{-12}$.

A naive hash is not safe

h = h * B + child without sorting is order-dependent and wrong (two orderings of the same multiset of children collide to different values when they should be equal). Summing child hashes without the per-height x[h] shift scramble collides trivially: children hashing to $a,b$ collide with any $a-1,b+1$. Both the sort-then-combine (AHU) and the random-shift-then-multiply (hashing above) structure are required, not optional simplifications.

Uses: count distinct subtree shapes (collect all ids), group equal subtrees, find all repeated subtrees (group by subtree hash), check a tree for symmetry, memoise DP over tree shapes, compare unrooted trees (hash at the centres), count non-isomorphic trees satisfying extra constraints via DP over canonical forms (distinct from the unconstrained enumeration below, which has a closed recurrence).

Automorphisms

The number of automorphisms of a rooted tree is ${\prod }_u{\prod }_{\text{class }K\text{ among }u\text{’s children}}|K|!$ times the product over children, i.e. at each vertex, children of the same class may be permuted. For an unrooted tree with one centre root there; with two centres $c_1{c}_2$, multiply the two rooted counts and double if the halves are isomorphic.

Proof: automorphism count

An automorphism of a rooted tree fixes the root, so it permutes the root’s children, mapping each child subtree to an isomorphic one. Conversely, choosing for each class of isomorphic children a permutation of that class ($|K|!$ ways), an isomorphism between the swapped subtrees, and an automorphism inside each child subtree, gives an automorphism; the isomorphisms between two isomorphic subtrees are in bijection with the automorphisms of one of them. Induction gives the product formula. For two centres, every automorphism maps the central edge to itself, either fixing or swapping its ends.

Prüfer codes

Encode: $n-2$ times, delete the smallest-labelled leaf and record its neighbour. Decode: degree of $v$ = 1 + occurrences in the code; repeatedly join the smallest current leaf (degree 1) to the next code entry. Both run in $O(n)$ with a pointer that only moves forward.

vector<int> pruferEncode(const vector<vector<int>>& adj) {    // n >= 2
    int n = sz(adj); vector<int> par(n, -1), order{n - 1}, deg(n), code;
    for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);   // root n-1
    for (int v = 0; v < n; v++) deg[v] = sz(adj[v]);
    int ptr = 0; while (deg[ptr] != 1) ptr++;
    for (int leaf = ptr, i = 0; i < n - 2; i++) {
        int nx = par[leaf]; code.push_back(nx);
        if (--deg[nx] == 1 && nx < ptr) leaf = nx;           // the neighbour became the smallest leaf
        else { while (deg[++ptr] != 1); leaf = ptr; }
    }
    return code;
}
vector<pair<int, int>> pruferDecode(int n, const vector<int>& code) {
    vector<int> deg(n, 1); for (int x : code) deg[x]++;
    int ptr = 0; while (deg[ptr] != 1) ptr++;
    int leaf = ptr; vector<pair<int, int>> edges;
    for (int x : code) {
        edges.push_back({leaf, x});
        if (--deg[x] == 1 && x < ptr) leaf = x;
        else { while (deg[++ptr] != 1); leaf = ptr; }
    }
    edges.push_back({leaf, n - 1});
    return edges;
}

Count (labelled vertices $\mathrm{1..}n$)	Value
trees (Cayley)	$n^{n-2}$
trees with degrees $d_1,\dots ,d_n$ ($\sum d_i=2n-2$)	$\left(\genfrac{}{}{0ex}{}{n-2}{d_1-1,\dots ,d_n-1}\right)$
trees in which $v$ is a leaf	$(n-1{)}^{n-2}$
rooted trees / rooted forests	$n^{n-1}$ / $(n+1{)}^{n-1}$
forests of $k$ trees with $\mathrm{1..}k$ in different trees	$k{n}^{n-k-1}$
spanning trees of $K_{m,n}$	$m^{n-1}{n}^{m-1}$
uniform random labelled tree	decode $n-2$ uniform random labels

Decoding $n-2$ uniform random labels samples a labelled tree uniformly in $O(n)$ — the standard way to generate tree test cases for stress testing, and far better than “add random edges, reject if a cycle forms,” which is both biased and slow. For spanning trees of an arbitrary (non-complete) graph, sample uniformly with Wilson’s algorithm (loop-erased random walks) instead, or count them exactly with the Matrix-Tree theorem — Prüfer codes only handle the complete-graph case, bijectively and constructively.

Proof: Prüfer bijection and the counting table

Bijection. A vertex is deleted only when it is a leaf, so it is recorded exactly $\mathrm{deg}(v)-1$ times (each recorded occurrence is the deletion of one neighbour, and its last remaining neighbour is never recorded for it unless it survives). Hence from the code we know every degree, and at each step the deleted leaf is the smallest vertex whose remaining recorded count is 0 among those not yet deleted: the decoder reproduces exactly the encoder’s choices, so encoding is injective. Any sequence decodes to a tree (each step joins a current leaf to a vertex that stays in the graph; $n-1$ edges without a cycle since each leaf is removed after use), and re-encoding returns the sequence, so it is a bijection between trees and $[n{]}^{n-2}$. Pointer: a new leaf smaller than ptr must be the vertex just recorded, and it is then the minimum; otherwise the next leaf is found by advancing ptr, which moves $\le n$ times overall.

Table. Degrees: codes with $v$ appearing $d_v-1$ times are counted by the multinomial. Leaf $v$: $v$ never appears, $(n-1{)}^{n-2}$. Rooted trees: choose a root, $n\cdot n^{n-2}$. Rooted forests: add a vertex $0$ joined to all roots, a bijection with trees on $n+1$ vertices. Forests with roots $\mathrm{1..}k$: delete the smallest non-root leaf $n-k$ times, recording its neighbour; the result is a sequence whose first $n-k-1$ entries are arbitrary and whose last entry is a root (after the last deletion only roots remain), and the same decoding argument makes this a bijection: $n^{n-k-1}\cdot k$. $K_{m,n}$: the Laplacian has eigenvalues $0$, $m$ ($n-1$ times), $n$ ($m-1$ times) and $m+n$, so by the matrix-tree theorem the count is $\frac{1}{m+n}{m}^{n-1}{n}^{m-1}(m+n)$. Uniform sampling: the decoder is a bijection from uniform sequences.

Counting unlabelled trees

Rooted unlabelled trees $r_n$ (1, 1, 2, 4, 9, 20, 48, 115, …) satisfy the Euler-transform recurrence $r_{n+1}=\frac{1}{n}{\sum }_{k=1}^n\left({\sum }_{d\mid k}d{r}_d\right)r_{n-k+1}$, and unrooted trees follow from Otter: $t_n=r_n-\frac{1}{2}({\sum }_{i+j=n}{r}_i{r}_j-[n\text{ even}]r_{n/2})$ (1, 1, 1, 2, 3, 6, 11, 23, 47, 106, …). $O(n^2)$ modulo a prime $>n$.

pair<vector<mint>, vector<mint>> countUnlabelledTrees(int N) {   // r[1..N] rooted, t[1..N] unrooted
    vector<mint> r(N + 1), t(N + 1), s(N + 1); if (N >= 1) r[1] = 1;
    for (int d = 1; d <= N; d++) {                            // s[k] = sum_{d | k} d r_d, filled once r_d is known
        if (d >= 2) { mint acc = 0; for (int k = 1; k < d; k++) acc += s[k] * r[d - k]; r[d] = acc / mint(d - 1); }
        for (int k = d; k <= N; k += d) s[k] += mint(d) * r[d];
    }
    for (int n = 1; n <= N; n++) {
        mint pairs = 0; for (int i = 1; i < n; i++) pairs += r[i] * r[n - i];
        if (n % 2 == 0) pairs -= r[n / 2];
        t[n] = r[n] - pairs / mint(2);
    }
    return {r, t};
}

Proof: Euler transform and Otter's formula

Rooted: a rooted tree on $n+1$ vertices is a root with a multiset of rooted subtrees of total size $n$, so $R(x)=x{\prod }_{k\ge 1}(1-x^k{)}^{-r_k}$. Taking the logarithmic derivative, $x{R}^{\prime }(x)/R(x)=1+{\sum }_{k}k{r}_k\frac{x^k}{1-x^k}=1+{\sum }_m{s}_m{x}^m$ with $s_m={\sum }_{d\mid m}d{r}_d$; comparing coefficients of $x^{n+1}$ in $x{R}^{\prime }=R(1+\sum s_m{x}^m)$ gives $(n+1)r_{n+1}=r_{n+1}+{\sum }_{k=1}^n{s}_k{r}_{n+1-k}$, the recurrence (the loop computes $r_d$ from $s_1..s_{d-1}$, all known). Otter (dissimilarity theorem): for any tree, $p-q+s=1$, where $p$ and $q$ count vertex and edge orbits under its automorphisms and $s=1$ iff some edge has its ends swapped by an automorphism. Automorphisms fix the centre (or the central edge as a set), so mapping each vertex orbit to the orbit of the edge leading towards the centre is well defined. With one centre $c$ it is a bijection between vertex orbits other than $\{c\}$ and all edge orbits, and $s=0$ (a swapped edge’s midpoint would be a fixed centre point between two vertices): $p-q=1$. With central edge $c_1{c}_2$ that is swapped ($s=1$), $\{c_1,c_2\}$ is one vertex orbit and the central edge an extra edge orbit outside the bijection: $p-q=0$. If it is not swapped ($s=0$), $c_1$‘s orbit is the only one left out (map $c_2$ to the central edge): $p-q=1$. Summing over all unlabelled trees on $n$ vertices: $\sum p=r_n$ (a tree with a chosen vertex orbit is a rooted tree), $\sum q$ = number of trees with a distinguished edge orbit = unordered pairs of rooted trees of total size $n$ = $\frac{1}{2}({\sum }_{i+j=n}{r}_i{r}_j+[n\text{ even}]r_{n/2})$, and $\sum s=[n\text{ even}]r_{n/2}$ (two equal halves). So $t_n=r_n-\frac{1}{2}(\sum r_i{r}_j-[n\text{ even}]r_{n/2})$.