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.
 (empty set) is always considered an IS because it technically fits the
definition. The sets
[C] are also ISs because no edge
contains only one vertex. The set
[B, C] also qualifies because there are no
C. One important thing to note is that the number of
ISs grows exponentially as the number of vertices grow. This has important
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.