What happens to the chromatic number of a graph, G, when one of its vertices, v, is deleted? By this I mean what will be the chromatic number of the subgraph G-v? I know that the chromatic number can remain the same or decrease by one but I do not know how to prove this. Can the chromatic number ever decrease by 2? If not how could I go about proving that it does not?
[Math] Chromatic number of a graph after a vertex is deleted from it.
coloringgraph theory
Best Answer
You want to prove that if we remove a vertex $v$ from the graph $G$, its chromatic number reduces by at most 1. By way of contradiction, suppose $\chi(G) = k$ and $\chi(G-v) \le k -2$. One way to color $G$ is by first coloring $G-v$ using $k-2$ or fewer colors and then by assigning a new color to vertex $v$. This gives a proper coloring of $G$ which uses $k-1$ or fewer colors, a contradiction.