# Probability proof and graphs

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:

Algorithm IndepSet(G):

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.

The argument follows from Step 3. You need only to argue that none of the vertices in $I$ are adjacent, but if they were, then you would not have completed Step 3 - "As long as the graph $H$ contains edges..." - which only terminates when $H$ is completely disconnected. Note also that it removes edges by removing vertices (rather than just the edge itself), therefore given vertices $u$ and $v$ in $V(H)$, if $(u,v)$ is not in $E(H)$, it was not in $E(G)$ to begin with.
Therefore for every distinct pair of vertices $u$ and $v$ in $I$, the edge $(u,v)$ is not in $G$, hence $I$ is an independent set.