Colored graph isomorphism reduction to uncolored graph isomorphism

Question

I am trying to find a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism. Doing a search on this problem, I found this article and it seems like theorem 1 is the solution I am looking for, however I don't fully understand it. Could someone please explain how the reduction works?

Answer 1

"a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism" ....

the below proof is due to Pascal Schweitzer,

Theorem 1 (reduction of colored to uncolored graph isomorphism). The graph isomorphism problem for colored graphs polynomial-time reduces to the uncolored graph isomorphism problem.

Proof: Assume we are given two colored graphs $G_1, G_2$ on $n$ vertices. If the sets of colors used for the graphs are not equal, we reduce the problem to a No-instance of uncolored graph isomorphism, i.e., some fixed pair of non-isomorphic graphs.

If the graphs use the same color set, we attach to every vertex a rooted tree, whose isomorphism type is in one-to-one correspondence with the color of the vertex: We choose a canonical bijection of the color set to the set of rooted trees for which every leaf is at height $⌈log2(n)⌉$ and which has a maximum degree of $3$. Such a bijection is given by the following method: We number the colors with integers in $\{0, . . . , n − 1\}$. To a color with binary encoding $ a_0 a_1 . . . a_{⌈log2 n−1⌉}$ we assign the tree for which every vertex on height $i$ has exactly $a_i + 1$ children. We obtain two new graphs $G′_ 1$, $G′ _2$ of size at most $O(n^2)$. By induction on the height, it is easy to show that these new graphs are isomorphic if and only if the original graphs are.