$G$, a graph, $k$-color-critical $\Rightarrow$ $G$ is connected

We let $G$ be a graph which is $k$-color-critical, meaning $\chi (G) = k$ and removing any vertex results in a graph with a smaller chromatic number.

My attempt has been to suppose that the graph $G$ is disconnected. From here I would then say that $G$ has connected components $G_1,G_2,...,G_n.$ Since I am trying to do a proof by contradiction, I assume that in this case I should be able to remove a single vertex and either end up with a graph that is still $k$-colorable or a graph which has chromatic number $\chi (G-v) < k-1$ for some vertex $v$.

I have shown that if $G$ is $k$-color-critical then by removing a single vertex $v$ from $G$ we get $\chi (G-v)=k-1$.

I am not sure exactly what to do from here.

I am thinking something along the lines of the induced subgraphs $G_1,...,G_n$ and if $G$ is $k$-colorable then the max of the chromatic numbers of the subgraphs would be $k$.

Correct me if I'm wrong, but this might be an other way to prove the statement by contradiction:

Suppose your k-critical-colored $$G$$ graph is not connected, then $$G$$ must have at least two connected components, let's call them $$G_1$$ ... $$G_n$$ with $$n \geq 2$$.

You know that, as minimum, one of those connected components must be k-colored, otherwise your graph wouldn't be k-colored. We will call this connected component $$G_1$$. Now, grab a different connected component (for example $$G_2$$) and take away one of its vertex. Did $$\chi(G)$$ change? Not really, because we left $$G_1$$ untouched therefore $$\chi(G_1)$$ didn't change so neither did $$\chi(G)$$. However, we did remove a vertex from the graph and that contradicts the critical graph definition, that is, removing any vertex will result in a chromatic color decay.

We assumed $$G$$ wasn't connected and we stumbled upon a contradiction therefore $$G$$ must be connected.

Suppose we delete a vertex from $G_1$. The resulting graph is $(k-1)$-colorable, so in particular its subgraphs $G_2, G_3, \ldots, G_n$ are all $(k-1)$-colorable. But if instead we delete a vertex from $G_2$, we similarly get that $G_1$ is $(k-1)$-colorable. We can then combine our $(k-1)$-colorings of the components to get a $(k-1)$-coloring of $G$, contradicting our assumption that $\chi(G)=k$.

• Got it. Start with $G_1$, kill a vertex, $G-v$ is $(k-1)$-colorable so all of the $G_2,...,G_n$ $(k-1)$-colorable. Then do process again $G_1$ $(k-1)$-colorable, so color all the connected components with $(k-1)$ colors so $G$ $(k-1)$ colorable, a contradiction. Thank you very much
– user43138
Commented Dec 5, 2012 at 11:39