
\problemdata     
{graphs-3}           
{graphs, colorability}              
{}              
{S02 in-class Week 4} 		
{S02 Radhika}        	




\begin{problem}
\newcommand{\dmax}{\ensuremath{dmax}\xspace}
\newcommand{\dmaxpr}{\ensuremath{dmax'}\xspace}

Prove that it is possible to color a graph $G$ with $\dmax +1$ colors,
where \dmax represents the maximum degree of any node in $G$.

\solution{
There are many different ways of proving this claim. Here we'll use
induction on the size of the graph. This approach also yields a recursive
algorithm for coloring the graph.

\begin{proof}
Let $P(n)$ be the predicate that it is
possible to color every $n$-vertex graph G with at most $\dmax +1$ colors.

\paragraph{Base case:} Consider a graph G with 1 vertex ($n=1$). This vertex has
degree zero, so $\dmax =0$. Since we can color that lone vertex with
$\dmax +1 =1 $ color, $P(1)$ holds.

\paragraph{Inductive step:} we assume $P(n)$ to prove $P(n+1)$.
Consider an $(n+1)$-vertex graph $G$ with maximum degree \dmax. Let
$G'$ be the graph obtained from $G$ by (temporarily) removing an
arbitrary vertex $v$ and all incident edges and let \dmaxpr be its
maximum degree. Since $G'$ now has $n$ vertices, we can apply the
inductive hypothesis which says that we can color it with at most
$\dmaxpr +1$ colors.

We now add vertex $v$ to get back $G$. This cannot \emph{decrease} the
maximum degree, so $\dmax \geq \dmaxpr$. Therefore, $\dmax +1$ colors
suffice to color all the nodes other than $v$ (that is, $G'$). As for $v$, since it can
have degree at most $\dmax$, it has at most $\dmax$ neighbors and we
have $\dmax +1$ colors at our disposal, so we can always pick one which
is not used by any of its neighbors.

This proves that $G$ is also colorable, hence $P(n+1)$ is true.


\end{proof}

Note that this theorem implies, for example, that a graph with
thousands of vertices, each of degree 3, requires at most 4 colors. So
for example the whole US worth of wireless devices would only require
a number of distinct frequencies comparable to the local radius
(neighborhood) of a single wireless device (as opposed to the number
of total devices).
}

\end{problem}

