. For a given a graph G = (V,E), a vertex cover of G is a subset of vertices C V such that each edge of G has at least one endpoint in C. The goal of the vertex cover problem is to find the optimal vertex cover C* with the minimum number of vertices. Consider the following randomized algorithm for vertex cover

Step 1: Start with C = empty set. Step 2: Pick an edge e uniformly at random from the edges that are not covered by C (i.e., if e has endpoints u and v, then {u, v} intersection C = . and add a random endpoint of e to C. Step 3: If C is a vertex cover, terminate and output C; else go to Step 2.

Answer the following questions: (a) Consider the very first iteration of the algorithm. What is the probability that a vertex from the smallest vertex cover C* is added to C? (Hint: for each edge e belong E, at least one endpoint of e must be in C*.)

(b) Consider the second iteration of the algorithm. What is the probability that a vertex from the smallest vertex cover C* is added to C? (Hint: you should discuss the two scenarios of whether a vertex from C* is added to C in the first iteration or not.)

(c) Let k be the number of vertices in the smallest vertex cover C*. Show that the expectation of the number of vertices of C is 2