We are given a graph $G = (V, E)$ with maximum degree $\Delta$ and a palette of $\Delta + 1$ colors
$\Gamma = \{c_1, \cdots , c_{\Delta+1}\}$. A coloring $\chi : V \rightarrow\Gamma$ assigns a color to every node in $V$ . We say that a coloring $\chi$ is
proper iff $\chi(u) ≠ \chi(v)$ for all edges $(u, v) \in E$. Show that there always exists a proper coloring in $G$.
I have no idea where to start on this problem and wanted some help. I have tried using contradiction but get stuck immediately. I thought we could possibly link it to matchings but not sure.
Best Answer
Here is an inductive argument. We induct on $n$, the number of vertices, that is, $n=|V|$. The base case, $n=1$, is trivial. Now, suppose, any $G=(V,E)$ with $|V|=n$ and $\max_{j\in V}{\rm deg}(j)=k$ is $(k+1)-$colorable. Take any $G'=(V',E')$ with $|V'|=n+1$. Select one vertex $u$, and look at the induced subgraph $G''=(V'\setminus\{u\},E'')$. This graph, by definition, has $n$ vertices, and due to inductive hypothesis is $(k+1)-$colorable. Now, keep this coloring, and add the vertex $u$ back. Since ${\rm deg}(u)\leqslant k$, there is a color which has not been used by any of the neighbors of $u$. Assigning this color to $u$ completes the induction.