# Removing a vertex from a non k-colorable graph cannot make it (k−2)-colorable

This is supposidly True in the key

but a pentagon is non-4-colorable and removing a vertex (either deletion or contraction) leaves a 2 colorable graph.

• What key?${}{}{}{}{}{}{}{}{}{}$ – user122283 Apr 3 '14 at 1:49
• A pentagon is $4$-colorable. Non $k$-colorable means you need more than $k$ colors to properly color the graph. – hbm Apr 3 '14 at 2:00
A pentagon is $C_{5}$. That is three-colorable. I begin at $v_{0}$ and color that red. I then color $v_{0}$'s neighbors, $v_{1}$ and $v_{2}$, blue. I then color $v_{1}$'s uncolored neighbor, $v_{3}$, red. I now have $v_{4}$, which is adjacent to $v_{2}$ (blue) and $v_{3}$ (red). So $v_{4}$ needs to be colored green. Thus, removing $v_{4}$ leaves a two-colorable graph- $P_{4}$, a path on four vertices.