I have this question in Graph Theory course, that I think I haven't understood well. the question is: Prove that the vertices of every connected graph on at least 8 vertices with maximum degree 6 can be colored with 3 colors so that no odd cycle is monochromatic.
I don't understand. If the graph contains K5 for example, or K4, there is no way I can color it with only 3 colors. What am I missing? Thanks.
By Brooks' theorem, since the graph has maximum degree $\le6$, is connected, and is not $K_7$, it has chromatic number $\le6$. Consider a proper vertex coloring with $6$ colors called red, orange, yellow, green, blue, and violet.
Now consider a new vertex coloring with only $3$ colors (red, yellow, blue) obtained from the aforementioned proper coloring by recoloring the orange vertices red, the green vertices yellow, and the violet vertices blue.
Let $C$ be a monochromatic cycle in the new coloring; I claim that the length of $C$ must be even. Without loss of generality, we can assume that the vertices of $C$ are red in the new coloring. Therefore, in the original proper coloring, they were alternately red and orange. Therefore the length of $C$ is even.