2. Given an undirected graph G=(V,E), a vertex cover of G is a subset of vertices CV such that, for every edge {u,v}E, either uC or vC. It turns out that, while finding a vertex cover of minimum size is difficult for general graphs, it can be done efficiently for trees using dynamic programming. (a) (25 pts) Describe the optimal substructure of this problem. In particular, given a tree T=(V,E), define the size of a minimum vertex cover in terms of smaller trees. Justify your answer. (b) (15 pts) Write pseudocode for a function treeVC(T) which returns a minimum vertex cover of T. (c) (5 pts) Analyze the asymptotic run time of your algorithm