Seja $G = (V, A)$ um grafo. Um conjunto de vértices $W\subset V$ é dito independente se $xy \notin A$ para todos $x, y \in W$.