Jtdylktuy

Theorem 10.10 of the textbook "A First Course in Graph Theory (2012)" by Gary Chartrand and Ping Zhang is as follows:

For every integer $k ge 3$, there exists a triangle-free graph with chromatic number $k$.

This is proved by induction on $k$ and in the inductive step it actually shows that

From a $(k-1)$-chromatic triangle-free graph $F$, Mycielski's construction produces a $k$-chromatic triangle-free graph $G$.

The Mycielski's construction (wiki) of $F$ is obtained from $F$ by first adding, for each vertex of $F$, a new vertex $v'$, called the shadow vertex of $v$, and joining $v'$ to the neighbors of $v$ in $F$ and then adding a new vertex $z$ and joining $z$ to all the shadow vertices.

For the part the correctness of $chi(G) = k$, it proceeds as follows:

Assume, to the contrary, that $chi(G) = k-1$. Let there be a $(k-1)$-coloring $c$ of $G$, say with colors $1, 2, ldots, k-1$. We may assume that $c(z) = k-1$. Since $z$ is adjacent to every shadow vertex in $G$, it follows that the shadow vertices are colored with the colors $1, 2, ldots, k-2$. For every shadow vertex $x'$ of $G$, the color $c(x')$ is different from the colors assigned to the neighbors of $x$. Therefore, if for each vetex $y$ of $G$ belonging to $F$, the color $c(y)$ is replaced by $c(y')$, we have a $(k-2)$-coloring of $F$. This is impossible, however, since $chi(F) = k - 1$.

My Problem: The argument in bold does not seem clear to me. How to make sure that the resulting coloring is a proper coloring? In other words, how to show that for each pair of adjacent vertices $u,v$ in $F$, $c(u') neq c(v')$?

The proof aims to show $chi(G) = k$ and has two parts.

First, they show that $chi(G) leq k$.

The second part of the proof is showing that $chi(G) geq k$. This is the part that concerns the bolded argument in your post.

To prove this, the authors suppose BWOC, that $chi(G) ngeq k$. Then there is a $k-1$ coloring of $G$. The vertex $z$ can be colored using the color $k-1$ and the shadow vertices can be colored using $k-2$ colors.

At this point the bolded statement comes in:
therefore, if for each vetex 𝑦 of 𝐺 belonging to 𝐹, the color 𝑐(𝑦) is replaced by 𝑐(𝑦′), we have a (𝑘−2)-coloring of 𝐹.

The authors are saying to give each vertex $y$ in $F$ the same color as their shadow vertex $y'$. Why do we know this is a proper coloring?
Since every vertex that is adjacent to $y$ in $F$ is also adjacent to $y'$ in $G$, then $y'$ must have a different color to every neighbor of $y$.

This fact essentially says that if we have a proper $k-1$ coloring of $G$, we don't have to use the color of $z$ (i.e. $c(z)$) for any of the vertices of $F$. So we would have a proper $k-2$ coloring of $F$ which is the desired contradiction.

Based on the assumption that $c(z)=k-1$, since $z$ is only adjacent to the set of shadow vertices of $F$, we know that the set of shadow vertices is $k-2$ colorable.

Now to address your question; When applying a proper coloring to a Mycielski's Constructed graph, it is possible to assign $c(y)=c(y')$. That is, a shadow vertex $y'$ can have the same color as $y$. This is because each shadow is not adjacent it's origin in the constructed graph.

Hence, because the set of shadow vertices is $k-2$ colorable, without any colors already imposed on $F$, we color $F$ so that $c(y)=c(y')$ for each $yin V(F)$. Thus, providing a $k-2$ coloring on $F$ which contradicts how $F$ was defined.