I'm not an expert, but I think you are confused about what 'independent set' means. It's basically 'no vertex pair v,w in the set has a edge (v,w)' So in your

I'm not an expert, but I think you are confused about what 'independent set' means. It's basically 'no vertex pair v,w in the set has a edge (v,w)' So in your loop example, you can take every other vertex in the loop and those form an independent set (of size n/2 ish). And n/2 is in Ω(n).