# Prove a statement about a Color-critical graphs.

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.

• Maybe we could prove this by squeezing the value for $\chi (G)-1 \leq \chi(G_{V-\{x\}})\leq \chi (G)-1$. If that is possible? Commented Apr 19, 2017 at 13:27
• The upper bound makes sense by definition, but I am not sure how to set up the lower bound. Commented Apr 19, 2017 at 13:28

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$.
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$.