Conceptually, an Independent Set (IS) is comparable to the inverse of a graph. It’s a set of vertices that do not contain both endpoints of any edge. Consider a connected graph with only three vertices as shown below. There are five independent sets.

The `[]`

(empty set) is always considered an IS because it technically fits the
definition. The sets `[A]`

, `[B]`

, and `[C]`

are also ISs because no edge
contains only one vertex. The set `[B, C]`

also qualifies because there are no
edges connecting `B`

and `C`

. One important thing to note is that the number of
ISs grows exponentially as the number of vertices grow. This has important
algorithmic implications.

At first glance, this concept seems a bit academic; however, ISs are useful in practice. Finding an IS is a way of asking, which vertices do not have a relationship. For instance, if vertices are people and edges are familial relationship, an IS would define people who are not related.