1. Review JE-J1 (load balancing section) upto the proof of Theorem J.1.
1.a Come up with examples that match the approximation ratio as closely as possible. Try small instances at first and then construct generic examples (in terms of 'n' -- the number of items).

2. Consider the following heuristic for constructing a vertex cover of a connected graph G: return the set of non-leaf nodes in any depth-first spanning tree of G. 
(i) Does it return a vertex cover of G?
(ii) Prove that this heuristic returns a 2-approximation to the minimum vertex cover of G by following these steps.

Let the number of internal nodes be denoted APPROX. Let OPT denote the size of the optimal VC of G.
Let T be any DFS traversal of G. Let VCT be any optimal vertex cover of T (not G) and OPTVCT denote its size.
Show that OPT >= OPTVCT.
Show that OPTVCT >= APPROX/2.
 
Hint: Show that
    (a) OPTVCT >= (n-L)/2 + 0.5 and
    (b) (n-L)/2 + 0.5 > APPROX/2 in which L denotes the number of leaf nodes of T.
Think: To prove (a), you need to start with a lower bound on OPTVCT -- what could lower-bound OPTVCT? What can say about VCT; e.g., can you assume that VCT has no leaf node?
Hint: Let I denote the number of internal nodes of T and J denote the number of internal nodes of T that are not in VCT. Do you observe how an upper bound on J can give a lower bound on OPTVCT?
Think: How to upper bound J? I was able to prove what is needed by starting with a trivial upper bound.
Think: What happens to your proof when your assumption about VCT having no leaf node fails?

(iii) Give an infinite family of graphs for which APPROX/OPT is as large a constant as possible.

Further hints for (ii):
All the degrees below are with respect to T.
(a) Show that any vertex cover of T can be modified to contain no leaf node. Hence, we can assume the same for VCT too.
(b) Use degrees of nodes in T to show that sum_{v in J} deg(v) >= 2I
(c) Use degrees of nodes in T to show that (n-1) >= 2I + L.
(d) Relate J and OPTVCT. Show that J = n - L - OPTVCT.

Further hints for (iii): Observe that trees can be good examples for which OPT is easy to determine. Try simple trees, e.g., a complete binary tree with k levels, or line graphs.