# Confusion about a proof on Mycielski construction and chromatic number

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 $$y\in V(F)$$. Thus, providing a $$k-2$$ coloring on $$F$$ which contradicts how $$F$$ was defined.