Approximation Algorithm for Independet Set Problem: Any Explanation Please?

Question

I am reading this note on approximation algorithms for independet set problem. I am confused of Theorem 1. and Corollary 3.

Here is the statement of Theorem 1.

Theorem 1 (Hastad [1]) Unless P = NP there is no $\frac{1}{n^{1-\epsilon}}$-approximation for MIS for any fixed $\epsilon>0$ where $n$ is the number of nodes in the given graph.

Here is the statement of Corollary 3.

Corollary 3 Greedy gives a $\frac{1}{\Delta+1}$-approximation for (unweighted) MIS in graphs of degree at most $\Delta$.

I feel like there is a contradiction between Theorem 1. and Corollary 3., no? Or because the graph in Corollary 3. is a special one with degree at most $\Delta$?

---

[1] J. Hastad. "Clique is Hard to Approximate within $n^{1-\epsilon}$"􀀀. Acta Mathematica, 182:105{142, 1999.

Answer 1

In general, the maximal degree in a graph can be as large as $n-1$. Therefore on general graphs, the greedy algorithm is only guaranteed to give a $1/n$ approximation, which you can also obtain by returning an arbitrary vertex.

What Corollary 3 does imply is that the graphs that Håstad uses have maximal degree $\Omega(n^{1-\epsilon})$.