Problem for showing a $k$-coloration of the graph $G$ Let $G$ be a $k$-chromatic graph and $$f: V (G) → [k]$$ a $k$-coloration of $G$.
Show that for each $i ∈ [1 ,. . . , k]$, there exists u ∈ $f^-1$[i] such that for each $j ∈ [1 ,. . . , k] / [i]$, there exists $v$ ∈ $N (u)$ of color $j$.
I have been quite a while stuck in this, problem. We just started to see colorations in graph, can someone give me an advice?
 A: here is an outline of the proof, hopefully you should be able to finalise it.


*

*Reason by contradiction.

*Start with a valid $k$-coloring, not verifying your property.

*You have one color $k$, such that for every vertex $u$ colored $k$, their neighbours don't use one color $j_u$.

*Can you change the $k$-coloring in order to use one less color (and remain a valid coloring) ?

*If so you will have a valid $k-1$ coloring of the graph, hence a contradiction.


Spoiler :

 Suppose that there is a color (for instance color $k$) such that for any vertex $u$ colored $k$ (i.e. $u\in f^{-1}(k)$), there exist one color $j\in \{1,\ldots, k-1\}$ such that $u$ has no neighbour with color $j$

Remark 

 Let $U=f^{-1}(k)$ be the set of vertices with color $k$. Note that because our coloring is a valid one, then the set $U$ is an independent set, i.e. for any two vertices $u,v\in U$ there is no edge between $u$ and $v$.

Changing the  coloring

 Now for any vertex $u$ in $U$, because there is one color $j_u$ not used by its neighbours, you can change its color from $k$ to $j_u$, and this will still be a valid coloring of the graph.

Finishing

 Because the set $U$ is an independent set, changing the coloring of $u$ won't affect the other vertices in $U$. Therefore they will still have the property of having one color not used by their neighbours, and you can iterate over all vertices in $U$.

Conclusion

 You've built a valid $k-1$ coloring of your graph $G$. But the chromatic number of $G$ is $k$. Hence a contradiction. 

