Prove a statement about a Color-critical graphs.

Question

A graph is called color-critical provided each subgraph obtained by removing a vertex has a smaller chromatic number. Let $G=(V,E)$ be a color-critical graph. Prove the following: $$\chi(G_{V-\{x\}})=\chi(G)-1.$$

I have been thinking about this for a long time but I am unable to come up with a specific approach. In some lecture notes, people have defined a color-critical graph using this statement and so no proofs are available online. Any hints as to how I should start with the proof will be much appreciated.

Answer 1

Since $G$ is color-critical, removing any vertex decreases the chromatic number, so $\chi(G-x) \leq \chi(G)-1$. Now suppose $G-x$ can be properly colored with $\chi(G)-2$ colors. Then this coloring can be extended to a coloring of $G$ in $\chi(G)-1$ colors by assigning $x$ a previously unused color, a contradiction. So $\chi(G-x) \geq \chi(G)-1$, and $\chi(G-x) = \chi(G)-1$.

Answer 2

You want to prove that removing a vertex from a color-critical graph reduces the chromatic number by $1$. Since the graph is color-critical, removing a vertex does reduce the chromatic number (by at least $1$). Hence, $\chi(G_{V-x}) \le \chi(G)-1$ for each vertex $x \in V(G)$.

Also, removing a vertex from a graph reduces its chromatic number by at most $1$ (this statement is true for all graphs, not just color-critical graphs). For if $\chi(G)=k$, and $G-x$ can be $(k-2)$-colored for some $x$, then the $(k-2)$-coloring of $G-x$ can be extended to a $(k-1)$-coloring of $G$ (by assigning vertex $x$ the new color $k-1$), contradicting the fact that $\chi(G)=k$.