How is Maximum Independent Set maximum-degree-approximative?

Question

a undirected graph $G=(V,E)$ is given and we want to find a maximum independent set $I$ with the following algorithm:

I = {}

for every vertex v in V:
    if v is not adjacent to any vertex from I:
        I.add(v)

return I

I want to show that this algorithm is max-degree-aproximative. So how can we show, that $|I|\geq \frac{Opt}{max-degree}$ is valid. My first idea was to set $|V|$ as an upper bound for $Opt$ ($\Rightarrow |V|\geq Opt$).

Would be cool if someone could help me. :-)

Answer 1

Welcome to MSE!

Your idea is a good one. Write $\Delta$ for the maximum degree. If we can show

$$\Delta |I| \geq |V| \geq \mathsf{OPT}$$ then we're done.

Say (towards a contradiction) that $\Delta |I| < |V|$. Then there must be some vertex $v$ which is not adjacent to any element of $I$ (do you see why?)

But then $v$ should have been added to $I$, and we contradict the definition of the algorithm.

---

I hope this helps ^_^