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
on the highlighted part I have received this comment how can I fix it? "Comment" : "Contrary to the needed equivalence, only one implication is being proved here."
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 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.
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).