thumb|Os nove vértices azuis formam um conjunto independente do grafo acima 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 .
Todo grafo tem ao menos um conjunto independente: o conjunto vazio. Um grafo pode ter vários conjuntos independentes distintos.
Se S é um conjunto independente de G e não existe um conjunto independente de G maior que S, diz-se que S é um conjunto independente máximo de G. O problema de, dado um grafo G, determinar se há um conjunto independente de tamanho k é um problema NP-completo.
Definição é Conjunto independente de
Características As seguintes indicações são equivalentes:
é um conjunto independente de é uma cobertura de vertices de é um conjunto independente de
Ver Teoria dos grafos
Categoria:Teoria dos grafos Categoria:Invariantes de grafos