1. Prove that a tree is a bipartite graph.
2. Prove that any tree can be two-colored.
3. Write an algorithm that deterimines if an arbitrary undirected graph is a bipartite graph. If the graph is bipartite, then your algorithm should also identify the vertices as to which of the two partitions each belongs to.