An independent set of an undirected graph G = (V,E) is a set of vertices U such that no edge in E is incident on two vertices of U.
(a) Give an efficient algorithm to find a maximum-size independent set if G is a tree.
(b) Let G = (V,E) be a tree with weights associated with the vertices such that the weight of each vertex is equal to the degree of that vertex. Give an efficient algorithm to find a maximum independent set of G.
(c) Let G = (V,E) be a tree with arbitrary weights associated with the vertices. Give an efficient algorithm to find a maximum independent set of G.