Clique-Width - Confusion over Proof I am working through some Graph Theory notes, and do not understand a line from the proof of a Theorem. Here is the statement of the Theorem.

$cw(G)=max\{cw(H)$ : $H$ is a prime induced subgraph of $G$$\}$.

The proof uses induction on $n=|V(G)|$ and starts by dealing with the case that $G$ is prime itself, which is easy to follow. It then continues as follows:

Let $G$ be non-prime, and let $M_{1},...M_{p}$ be maximal non-trivial modules of $G$. By contracting each $M_{i}$ into a single vertex $m_{i}$ we obtain the characteristic graph $G_{0}$ of $G$. We separately  construct expressions representing the graphs $G_{0}$ and $G[M_{i}]$ for each i, assuming by the induction that each expression uses at most $max\{cw(H)$ : $H$ is a prime induced subgraph of $G$$\}$ different labels. If in the expression defining $G_{0}$ the vertex $m_{i}$ is created with label $j$, we finish the construction of the graph $G[M_{i}]$ by renaming all labels to $j$. Then in the tree describing $G_{0}$ we replace the node creating $m_{i}$ with the root of the tree creating $G[M_{i}]$. The resulting tree represents $G$ and uses at most $max\{cw(H)$ : $H$ is a prime induced subgraph of $G$$\}$ labels, as required. $\square$

Ok so here are my thoughts. It agree that the construction of each $G[M_{i}]$ requires at most $max\{cw(H) \space : \space H$ is a prime induced subgraph of $G\}$ labels, by the induction hypothesis and the fact that any prime induced subgraph of $G[M_{i}]$ is a prime induced subgraph of $G$. But when constructing $G$ by taking the construction of $G_{0}$ and 'editing' in the sub-constructions of the $G[M_{i}]$, we have to make sure that the labels used in construction of each $G[M_{i}]$ have not already been used in the construction of $G$. For instance, when we come to the creation of the last vertex $m_{p}$ of $G_{0}$, although we may only need less than or equal to the required number of labels for the construction $G[M_{p}]$, these labels have to be chosen to not 'clash' with the labels occupied by the previous $m_{i}$, so we cannot be sure we are not using too many labels?
Would really appreciate some help on this.
Thanks
Misha:

 A: From the point of view of the formula:
If $X$ is an expression for creating $G[M_i]$, then $\rho_{1 \to j}(\rho_{2 \to j}(\dots \rho_{k \to j}(X)\dots))$ is an expression for creating a $G[M_i]$ with all vertices labeled $j$.
In the description for $G_0$, if we replace the vertex creation $j (m_i)$ with the expression $\rho_{1 \to j}(\rho_{2 \to j}(\dots \rho_{k \to j}(X)\dots))$, then instead of creating a single vertex $m_i$ with label $j$, we'll get all of $G[M_i]$. Then, because the labels are the same, the edges between $G[M_i]$ and the rest of $G$ will all be the same as the edges between $m_i$ and the rest of $G_0$, exactly what we want from a module.
Order of operations ensures that whatever happens in $\rho_{1 \to j}(\rho_{2 \to j}(\dots \rho_{k \to j}(X)\dots))$ does not affect the rest of the formula.
From the point of view of the tree:
The creation of $G[M_1], G[M_2], \dots$ are happening in separate subtrees. When we do a relabeling $\rho_{i \to j}$, a edge join $\eta_{i,j}$, or anything else, that node only affects the things in the subtree below it. So we don't have to worry about the same labels being used for a different purpose in another subtree.
And no matter if we're looking at a single $j(m_i)$ node, or a complicated subtree creating a uniformly $j$-labeled $G[M_i]$, the next thing we see above it is a disjoint union node connecting it to the rest of the graph. That is what separates labels in the subtree from labels used anywhere else.
