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.

  • $\begingroup$ What's the source of this problem, please? $\endgroup$ Commented May 11, 2014 at 11:57
  • $\begingroup$ 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 ? $\endgroup$ Commented May 11, 2014 at 13:35
  • $\begingroup$ I tried to find an example and i see that it will be the same but i couldnt prove it theoretically! Any help please $\endgroup$ Commented May 11, 2014 at 21:47
  • $\begingroup$ What I meant was, where did you find this problem? $\endgroup$ Commented May 11, 2014 at 23:06
  • $\begingroup$ In my work on the stage i have something like that related to forests ... but this is a little bit general. $\endgroup$ Commented May 12, 2014 at 2:09

1 Answer 1


The problem is false, Indeed, Consider a cycle of 5 vertices colored by the colors 1,2,1,2,3 then the third vertex colored by color 1 and not adjacent to the color 3, but removing it obtain a path which can be colored by 2 colors.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .