Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. A subset $I$ of $V$ is called an independent set if for any two distinct vertices $u$ and $v$ in $I$, $(u, v)$ is not an edge in $E$.
Let $n$ and $m$ denote the number of vertices and edges in $G$, respectively, and assume that $m ≥ n/2$.
Consider the following algorithm, in which all random choices made are mutually independent:
Step 1: Set $H = G$.
Step 2: Let $d = 2m/n$. For each vertex $v$ of $H$, with probability $1−1/d$, delete the vertex $v$, together with its incident edges, from $H$.
Step 3: As long as the graph $H$ contains edges, do the following: Pick an arbitrary edge $(u, v)$ in $H$, and remove the vertex $u$, together with its incident edges, from $H$.
Step 4: Let $I$ be the vertex set of the graph $H$. Return $I$.
• Argue that the set $I$ that is returned by this algorithm is an independent set in G.
Any help appreciated. Have thought of anything even to get the question started over the past 6 hours.