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

-

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 – Frudrururu Dec 5 '12 at 11:39