Vrftjkry

Let $G$ a graph and $k= chi(G)$. Prove that for all $k$-colorings of $G$ and for all colors
$i in {1,ldots,k} $, there exists $u in V(G)$ of color $i$ such that for every $j in {1,ldots,k}$ $i$, there exists $v in N(u)$ of color $j$.

What I have to show is that for every color of the graph, there is always a vertex of that color so that it is a neighbor of all other colors.

I have tried to prove by contradiction. The contradiction would occur in that if there is no vertex for which this would be fulfilled then the chromatic number would be smaller. I start by saying "Let $C_{1}$ be the set of vertices of color graph $1$, so let's suppose that ..." and there's the problem, I really do not know whether to suppose that there is a vertex that has all colors as neighbors except him same and another different, or that all the vertices in $C_{1}$ fulfil this property, or if some, etc, I am totally confused.

The other way is by induction, the base step would be for two or more (considering that the graph is not a single vertex) but I do not know how to use the induction hypothesis to prove the case of $k + 1$ colors.

I would appreciate any help.

Let $G$ be a graph with $chi(G)=k$. Pick a vertex $v$ of colour $i$, then suppose all its neighbour is not of the other colors, then there is a color $ineq j in {1,2...k}$ that hasen't been used by the neighbours of $v$. We can then color $v$ color $j$. And since we can do it for all vertices of colour $i$(because we assume there is no vertices of colour $i$ whose neighbours are all of the other colors), we can just replace vertices with color $i$ with some other colours in ${1,2,...,k}/ {i}$. We can do it because vertices of the same colour are not adjacent hence they won't affect each other. Well then that says $chi(G)<k$. Contradiction! Hope I didn't made any mistake... I'm learning as well.

First, observe that there is a small glitch in the statement of the problem. "Prove that for all $k$-colorings of $G$ and for all colors $i in {1,ldots,k} setminus {i}$,..." should not have the "$setminus {i}$" at the end. The claim is about every $k$-coloring and every color.

Next, the idea of proving the claim by contradiction is a good one, as shown in @mathnoob's answer. You were on the right track, but then got confused. This is likely due to the fact that the claim you try to prove has several quantifiers in it: for all colorings, for all colors, there exists a vertex, such that for every other color....

In cases like these, it's useful, especially if you are realtively new to proofs, to start by writing down the negation of the claim you want to prove. Let's do it for the problem at hand:

Suppose there exist a $k$-coloring of $G$ and a color $i in {1,ldots,k}$ such that, for every vertex $u in V(G)$ of color $i$, there exists a color $j in {1,ldots,k} setminus {i}$ such that no vertex $v in N(u)$ has color $j$.

This unambiguously states the assumption that is supposed to lead to a clash with the assumption that $chi(G) = k$. In fact, as pointed out in @mathnoob's answer, you can change the color of $u$ from $i$ to $j$ while preserving a valid coloring. Once this has been done for all vertices of color $i$, the resulting coloring has $k-1$ colors: contradiction!