Dado un grafo G, un subconjunto de vértices H ⊂ V(G) se llama conjunto independiente si no hay dos vértices en H que sean adyacentes.