A graph with isolated vertices has a maximum independent set of size 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 vertices and edges has a maximum independent set of size at least .

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 edges *and* an independent set of size .

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

### Like this:

Like Loading...

*Related*