\problemdata
{S00 ps4}
{bipartite graph}

\begin{problem}
  A 2-colorable graph is called {\em bipartite} (two pieces).

\begin{problemparts}
  \problempart Prove by induction that every tree is bipartite.
  \solution{
  We first prove the following claim:

\begin{lemma*}
By a {\em leaf} in a graph, we mean a vertex of degree $1$.
We prove that every tree on at least $2$ nodes has a leaf.
\end{lemma*}
\begin{proof}
Let $T$ be a tree, and let $P$ be a simple path in $T$ of maximum
length.  (Because we disallow repeated vertices, the length of any
simple path is upper-bounded by the number of vertices in $T$.  This
implies there must be at least one simple path with maximum length.)

Suppose that $P = \{v_1, v_2 \ldots, v_k\}$ in this order.  We claim
that $v_1$ is a leaf.  For if not, then there is an edge $(v,v_1)$ in
$T$, where $v \neq v_2$.  Now if $v \not\in P$, we can attach $v$ to
the end of $P$ to obtain a longer path --- a contradiction.  But if $v
\in P$, then since $v \neq v_2$, this will give a cycle in $T$ ---
also a contradiction.
\end{proof}
Given this fact, we prove the theorem by induction on $n$.
\begin{proof}
Base case: $n = 1$.  We can color the single node anything we want,
thereby using at most two colors.

Inductive step.  Suppose that we know that every tree on $n$ nodes
is bipartite, for some $n \geq 1$.  Let $T$ be a tree on $n+1$ nodes;
we need to show how to two-color it.  Since $n+1 \geq 2$, we know
that $T$ has a leaf $v$.  Let $w$ be the unique neighbor of $v$.
Let $T' = T - \{v\}$.  Note that $T'$
is a tree, since it is still connected and has no cycles.
Thus, by the induction hypothesis, we can two-color it.  

Now we define the following two-coloring of $T$.  If $u$ is a vertex
of $T$ not equal to $v$, give $u$ the color that it had in our 
two-coloring of $T'$.  Then give $v$ whichever color we didn't give
to its neighbor $w$.  As this is a valid two-coloring of $T$, this
completes the inductive step and the proof.
\end{proof}
}


  \problempart Prove that a graph is bipartite if and only if every simple
  cycle is of even length. ({\bf Hint:} Can $v$ have both an even and
  an odd length path to $w$?)

\solution{
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$.  Now 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 two adjacent nodes are either in the same set $S_i$
--- which we are going to show can't happen --- or are in two
consecutive sets $S_i$ and $S_{i+1}$ that are colored differently.
This is true because if one vertex gets included in $S_i$ before its
neighbor is colored, then the neighbor will be colored in the next
step.

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$.  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 cycle has length $2i+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.  
}

\problempart Explain why (a) follows immediately from (b).
\solution{
Since a tree has no simple cycles, it has no simple cycles of odd
length, and thus (a) follows directly from (b).
\end{solution}
}

\end{problemparts}
\end{problem}