Answered You can hire a professional tutor to get the answer.
(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...
(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 + ). )
