# 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? – Gerry Myerson May 11 '14 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 ? – mohamad nasser May 11 '14 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 – mohamad nasser May 11 '14 at 21:47
• What I meant was, where did you find this problem? – Gerry Myerson May 11 '14 at 23:06
• In my work on the stage i have something like that related to forests ... but this is a little bit general. – mohamad nasser May 12 '14 at 2:09