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?

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. 

