3. A vertex set I-V in a graph G = (V. E) is called independent if no two vertices in I are adjacent. Given a graph G = (V, E), we would like to find a maximum independent set. Consider the following greedy algorithm. begin while X do uan arbitrary vertex in X for every edge {u, v} incident to u do return I (a) Show that this algorithm returns an independent set of G = (V,E) (b) Show that it does not always return a maximum independent set (c) How small can the ratio |I|/Imax be over all graphs, where I is the independent set returned by the algorithm and Imax is a maximum independent set? (In other words, how far can the algorithm be from the optimal solution, in the worst case?) 3. A vertex set I-V in a graph G = (V. E) is called independent if no two vertices in I are adjacent. Given a graph G = (V, E), we would like to find a maximum independent set. Consider the following greedy algorithm. begin while X do uan arbitrary vertex in X for every edge {u, v} incident to u do return I (a) Show that this algorithm returns an independent set of G = (V,E) (b) Show that it does not always return a maximum independent set (c) How small can the ratio |I|/Imax be over all graphs, where I is the independent set returned by the algorithm and Imax is a maximum independent set? (In other words, how far can the algorithm be from the optimal solution, in the worst case?)