\problemdata     
{S01-PS4-6}           
{graphs, coloring}
{}              
{S01-PS4} 		
{S01 Karger}

\begin{problem}

 \textbf{Graph Coloring}

Argue that a graph is 2-colorable if and only if every simple cycle is of
even length.

\solution{
  \begin{proof}
    Assume a graph has a simple cycle of odd length. Let the cycle be
    $v_1,v_2,\ldots, v_n,v_1$, where $n$ is odd. Suppose that two
    colors (red and blue) sufficed to color the graph containing this
    circuit.  Without loss of generality let the color of $v_1$ be
    red. Then $v_2$ must be blue, $v_3$ must be red, and so on, until
    finally $v_n$ must be red (since $n$ is odd). But this is a
    contradiction, since $v_n$ is adjacent to $v_1$. Therefore at
    least three colors are needed. Hence a graph is 2-colorable only
    if every simple cycle is of even length.
  
    Conversely, assume the graph has no simple cycle of odd length. We
    show that it is possible to color the graph using two colors.
    Without loss of generality, assume that the graph is connected.
    (As otherwise we can repeat the argument for each connected
    component of the graph). Select a node, say $m$, in the graph and
    color it red.  Color all the nodes adjacent to $m$ blue. (Call the
    set of all such nodes $S_1$.) Color all the nodes that are
    adjacent to the nodes in $S_1$ but have not yet been colored, red.
    (Call the set of all such nodes $S_2$.)  Continue this process
    until you have colored all the nodes. We now show that no two
    nodes in $S_i$ are connected by an edge, for all $i$. (This is
    sufficient to establish that our coloring is valid, since by
    construction we cannot have two adjacent nodes that were colored
    identically but do not belong to the same set $S_i$.) Assume that
    we can find two nodes $u$ and $w$ in some set $S_i$ that are
    adjacent in the graph. If $u$ and $w$ are adjacent to a node in
    $S_{i-1}$ then we have a simple cycle of length $3$, which is
    impossible.  So let $u_{i-1}\neq w_{i-1} \in S_{i-1}$ be nodes
    adjacent to $u$ and $w$ respectively.  Now if $u_{i-1}$ and
    $w_{i-1}$ are adjacent to a single node in $S_{i-2}$, say $c$,
    then $u,u_{i-1},c,w_{i-1},w,u$ is a simple cycle of length 5,
    which is impossible.  So let $u_{i-2}\neq w_{i-2}\in S_{i-2}$ be
    nodes adjacent to $u_{i-1}$, and $w_{i-1}$ respectively.
    Continuing this way we arrive at nodes $u_1\neq w_1 \in S_1$.
    However these are adjacent to $m$.  But this gives us a simple
    cycle $m,u_1,u_2,\ldots,u_{i-1},u,w,w_{i-1},w_{i-2}\dots,w_1,m$,
    where $u_j,w_j\in S_j$. But this cyle has length $2 i+1$, which is
    odd, hence a contradiction. Therefore, for all $i$ we do not have
    two nodes in $S_i$ that are connected by an edge.  Therefore our
    coloring is valid.
  \end{proof}}

\end{problem}
