A Proof of Theorem 4

A special case of Lemma 8 is given in Lemma 16. Then, we prove Lemma 8. Lastly, Section A.2.1 We prove the claim by induction on m. Induction step: Assume the claim holds for m 1. Continue until you obtain a subset of size at most m. We now bound the number of iterations required. Lemma 17. F or any c R, there exists some x Following the proof of Lemma 5.4 in [11], we have that when event A holds, null 1 2 I (X Step 2 S contains all of the neighbors of u.