About last part of proof of Brooks' theorem in a course in combinatorics I am reading the proof of Theorem 3.1, which is Brooks' Theorem. I cannot understand the last part of the proof, which is on p.26 (link at google book). I don't understand what is $C_{ij}'$.
I thought it was defined as the component containing $x_i$ and $x_j$ when considering the induced subgraph $H_{ij}$ with colors $i$ and $j$. But on p.26, "Clearly $a \in C_{23}'$ (since $x_1$ now has color $3$)." seems to contradict my guess since $a$ is not between the $x_2$ and $x_3$ and "(since $x_1$ now has color $3$)" won't make sense.
Please help.
 A: You’re confusing $C_{ij}'$ with $C_{ij}$. It’s defined like $C_{ij}$, but in terms of the new coloring after colors $1$ and $3$ have been interchanged.
Let $H'$ be the graph $H$ after the colors $1$ and $3$ have been interchanged on the subgraph $C_{13}$. For colors $i$ and $j$ we define $H_{ij}'$ to be the subgraph of $H'$ induced by the colors $i$ and $j$, and we define $C_{ij}'$ to be the commponent of $H_{ij}'$ that contains the vertices in $\Gamma(x)$ that are colored $i$ and $j$. Vertex $x_1$ has color $3$ in $H'$, and vertex $x_2$ still has color $2$, so $C_{23}'$ contains $x_1$ and $x_3$. And since vertex $a$ has color $2$ and is adjacent to $x_1$, it must also be in $C_{23}'$.
Just to complete the argument, the only vertex in $C_{12}$ that has changed color is $x_1$, so removing it and the edge $x_1a$ from $C_{12}$ leaves a path from $a$ to $x_2$ colored only with colors $1$ and $2$. This path must be part of the component $C_{12}'$ of $H_{12}'$, so $a\in C_{12}'$, and $C_{12}'\cap C_{23}'\ne\{x_2\}$, contradicting what was established earlier in the proof.
