Page 331 Exercise 2

Demonstrating that all trees are bipartite is a relatively simple task.  Assume that we mark the root vertex with a one.  Also assume that we mark each of its children with a zero.  Because only one simple path exists between any two vertices in a tree, each vertex will appear on only one adjacency list.  This means that each vertex is either an unmarked child or a previously visited parent.  If it is an unmarked child, it will be given the opposite mark of its parent.  If it is a previously visited parent it will have the opposite sign of the child.  A mismatch can occur
only if there is more than one path between any two vertices.  This means that the graph is not a tree, which is a contradiction.