        \problemdata       % Takes 5 *mandatory* arguments
        {bipartite-trees}             % latex-friendly label for the prob.
        {str. induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut5-3, S00 PS4} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
A 2-colorable graph is called {\em bipartite}.  Prove by
induction that every unordered unrooted tree is bipartite. The set of
{\em unordered unrooted} trees $T$ is defined recursively as follows:

1.  A single node is in $T$.

2.  If $t_1$ and $t_2$ are two disjoint trees in $T$, then the tree
    $t'$ formed by adding an edge from any vertex $v$ of $t_1$ to any
    vertex $u$ of $t_2$, is also in $T$.

\solution{
\begin{proof}
We want to prove that a tree is 2-colorable.  If we do this, then we
have shown that a tree is bipartite.  We will prove this using
structural induction.

{\bf Base case:} The base case is trivially true.  A single node can be
colored with just one color, meaning that it is two-colorable, and
therefor bipartite.

{\bf Structural Induction Step:}
Using rule 2 in the definition of an unordered,
unrooted tree, any tree is constructed out of two smaller trees, $t_1$
and $t_2$. Each of these trees, by our inductive hypothesis, is 2-colorable.
Can we join $u$ from $t_1$ and $v$ from $t_2$ in a way such that our
new tree is also 2-colorable?  To do this, $u$ and $v$ must be
different colors.

Consider a 2-coloring of each of the smaller trees.  If vertex $v$
is a different color from $u$, then we can connect the
two trees to form the larger tree, and we are done.  If they are
different colors, then switch the coloring in $t_2$.  Now $u$ and $v$
are different colors, and can be connected.  Thus all possible trees
that can be constructed using the recursive definition must be 2-colorable.
\end{proof}
}

\end{problem}
