(a) Let G be a graph on n vertices with average degree d. Prove that G has an independent set of siz

(a) Let G be a graph on n vertices with average degree d. Prove that G has an independent set of size at least n/2d. (Hint: Delete every vertex of G independently with probability p. How many edges are left between the remaining vertices. Modify the set of the remaining vertices to make it an independent set. Optimize p to maximize the cardinality of the independent set you obtained. ) (b) Fix > 0. Let G be a graph on n vertices with average degree 3. Tune your argument in part (a) into a linear-time (both in n and in 1/) randomised algorithm which, with probability at least 99%, nds an independent set of G of size at least n(1?)/6. (Hint: Assume that X is a random variable with EX ? µ, and X ? cµ always, where µ > 0 and c > 1. Show that P(X ? (1?)µ) ? 1?/(c?1 + ). )