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.
Best Answer
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 $i\neq 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.