Complemento de um grafo

---

O complemento de um grafo $G$, representado por $\bar{G}$, é um grafo de possui o mesmo conjunto de vértices do grafo original, mas com as conexões de arestas invertidas.

De forma mais simples, para criar o complemento de um grafo:

• Vértices: Você mantém exatamente os mesmos vértices do grafo original.
• Arestas: Você inverte todas as conexões. Se dois vértices estavam conectados por uma aresta no grafo original ($G$), eles não estarão conectados no complemento ($\bar{G}$). E se dois vértices não estavam conectados em $G$, eles estarão conectados em $\bar{G}$.

Exemplo:

NOTE

O grafo $G$ a esquerda e seu complemento à direta.

Referências

---

Teoria dos grafos - Conceitos iniciais