(Solved): 2. Given an undirected graph \( G=(V, E) \), a vertex cover of \( G \) is a subset of vertices \( ...

2. Given an undirected graph \( G=(V, E) \), a vertex cover of \( G \) is a subset of vertices \( C \subseteq V \) such that, for every edge \( \{u, v\} \in E \), either \( u \in C \) or \( v \in C \). 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 \( \operatorname{treeVC}(\mathrm{T}) \) which returns a minimum vertex cover of \( T \) (c) (5 pts) Analyze the asymptotic run time of your algorithm.