Abstract :

Tur\'{a}n's theorem says that sparse graphs have large independent sets. We discuss a proof of this theorem due to Erd\"{o}s. We make a similar statement for a generalization of maximum independent set problem. We will also mention other results about the algorithmic complexity of this generalization.