# Another theorem of Turán

A graph with ${n}$ isolated vertices has a maximum independent set of size ${n}$ and a complete graph has a maximum independent set of size 1. As you increase the number of edges, you should get smaller and smaller maximum independent sets.

This intuition is quantified by a theorem by Turán that says that a graph with ${n}$ vertices and ${e}$ edges has a maximum independent set of size at least ${\frac{n^2}{2e+n}}$.

In particular, graphs with linear number of edges, for example, planar graphs, or graphs with max. degree bounded by a constant are guaranteed to have a linear sized independent set.

Note that the theorem only says that small number of edges guarantees a large independent set. The converse is not true, i.e., a large independent set does not imply a small number of edges. Example: complete bipartite graphs. They have ${\frac{n}{2}^2}$ edges and an independent set of size ${n/2}$.

Also, the theorem is constructive. So you can actually find the independent set in question in polynomial time.