Can someone explain what is this proof of AHU algorithm for tree isomorphism means?

Question

Theorem: The canonical number of a rooted tree is an isomorphism invariant, i.e., (T1; r1) ≡ (T2; r2) iff their canonical numbers are the same

Proof: The proof is by induction on the level number of the nodes;the base case is obvious. Since any isomorphism permutes the children of the root, the ordering of the canonical numbers of the children is unique up to permutations that permute the children with the same canonical number. By the inductive hypothesis, their canonical numbers are isomorphism invariant, thus the canonical number associated with the root is isomorphism invariant as well.

Answer 1

I'll use "tree" where I mean "rooted tree". I'm going to use the following lemma:

---

Lemma: If $x_1,\dots,x_n$ and $y_1,\dots,y_m$ are lists of canonical numbers ordered by size, then the concatenations $x_1x_2\cdots x_n=y_1y_2\cdots y_m$ if and only if $n=m$ and $x_i=y_i$ for all $i$.

Proof: I'll leave this as an exercise to you. You could use induction again.

---

Proof of AHU: The proof is by induction on the height of the tree, so it starts with the base case of a tree of height $1$:

If $(T_1;r_1)\equiv (T_2;r_2)$ are two trees of height one, they are automatically isomorphic, since they can only consist of the single root node. Since the roots of both trees are leaves, they both get the same canonical number 10. So yes, nothing fancy can happen in the base case.

Now suppose that every two trees of height $\leq n$ have the same canonical numbers iff they are isomorphic, then we want to show that two trees of height $n+1$ also have the same canonical numbers iff they are isomorphic.

Let $(T_1;r_1)\equiv (T_2;r_2)$ be two trees. Then there exists an isomorphism $f:T_1\to T_2$ if and only if

• $f$ sends $r_1$ to $r_2$ and
• $f$ is a bijection between the children of $r_1$ and the children of $r_2$ and
• $f$ restricted to each subtree generated by some child $c_i$ of $r_1$ is an isomorphism to the subtree generated by $f(c_i)$.

But the subtree generated by a child $c_i$ has height $\leq n$, so by induction hypothesis these subtrees are isomorphic if and only if $c_i$ and $f(c_i)$ have the same canonical number.

Then by the lemma the list $x_1,\dots,x_n$ of canonical numbers of children $c_i$ of $r_1$ is the same as the list $y_1,\dots,y_n$ of children $f(c_i)$ of $r_2$ if and only if ordering them and concatenating them results in the same canonical number.

But these resulting concatenations are equal if and only if $T_1$ and $T_2$ have the same canonical number (since the canonical numbers of $T_1$ / $T_2$ is just the concatenation with a $1$ put in front and a $0$ at the back).