Na teoria dos grafos, um conjunto independente de um grafo é um conjunto de vértices de tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se e são vértices quaisquer de um conjunto independente, não há aresta entre e .