# coloring of a graph after removing a vertex

Let $G$ be any simple graph (i.e has no loops nor multiple edges) and let $1,2,...,\chi(G)$ be any good coloring to the vertices of $G$(i.e a minimal coloring for its vertices in which each 2 adjacent vertices have different colors).

let $v$ be a vertex in $G$ of color $1$ such that $v$ has no neighbors of color $2$.

show that $\chi(G-\{v\})=\chi(G)$.

Thank you for helping.

• What's the source of this problem, please? Commented May 11, 2014 at 11:57
• my problem is that if i color the vertices of a graph (in which each 2 adjacent vertices have different colors and with minimal number of colors ) and i want to remove a vertex such that there is some color not obtained in its neighbors , Did the chromatic number still the same? or it will decrease one ? Commented May 11, 2014 at 13:35
• I tried to find an example and i see that it will be the same but i couldnt prove it theoretically! Any help please Commented May 11, 2014 at 21:47
• What I meant was, where did you find this problem? Commented May 11, 2014 at 23:06
• In my work on the stage i have something like that related to forests ... but this is a little bit general. Commented May 12, 2014 at 2:09