A vertex cover of a graph G = (V,E) is a subset of vertices V such that each edge in E is incident on at least one vertex of V .

(a) Give an efficient algorithm to find a minimum-size vertex cover if G is a tree.

(b) Let G = (V,E) be a tree such that the weight of each vertex is equal to the degree of that vertex. Give an efficient algorithm to find a minimum-weight vertex cover of G.

(c) Let G = (V,E) be a tree with arbitrary weights associated with the vertices. Give an efficient algorithm to find a minimum-weight vertex cover of G.