1. Given a graph G = (V, E) a k-coloring of G is a labeling of the vertices with the colors C1,C2,...,Ck such that for every edge (u, v) the color of u is different from the color of v. (a) Give a linear time algorithm that finds a 2-coloring for a tree. (b) Think about coloring a tree with two colors so that you have the maximum number of nodes colored c. Prove that your algorithm from part (a), with a minor modification probably, can be used to solve this problem. Be precise. (c) Show an example of a tree, T, that can have at most j nodes colored c in a 2-coloring but T can have j'> j nodes colored c in a 3-coloring. Try to find the smallest example of such a tree T. (d) Give a linear time dynamic programming algorithm that creates a 3-coloring for a tree such that the maximum number of nodes are colored c1. Justify your