Grafo complemento

En teoría de grafos, el grafo complemento o complementario de un grafo es otro grafo, con el mismo conjunto de vértices del original, y tal que dos vértices están conectados por una arista si y solo si esa arista no existe en el primero.

[1]​ Para obtener el complemento de un grafo, se pueden completar todas las aristas faltantes para hacerlo completo, y quitar todas las aristas del grafo G original.

[1]​ Este concepto no debe confundirse con el del complemento de un conjunto, pues solo se complementan las aristas.

Por definición, los conjuntos de aristas de un grafo y su grafo complemento forman una partición; es decir, su intersección es vacía y su unión es el conjunto de todas las aristas posibles que tendría el grafo completo del mismo número de vértices.

Si dos vértices de un grafo no están conectados por aristas, el grafo inverso conservará dicha ausencia de aristas, mientras que el grafo complemento los conectará con aristas en ambos sentidos.

Asimismo, si dos vértices de un grafo dirigido están conectados en ambos sentidos, el grafo inverso conservará dichas aristas, mientras que el grafo complemento eliminará las aristas entre ambos vértices.