Un grafo autocomplementario es un grafo que es isomorfo a su complemento . Los gráficos autocomplementarios no triviales más simples son una ruta de 4 vértices y un ciclo de 5 vértices .
Cualquier gráfico de Paley es autocomplementario [1] . Por ejemplo, un gráfico de torre de 3 × 3 (gráfico de Paley de noveno orden) también es autocomplementario debido a la simetría que mantiene el vértice central en su lugar, pero intercambia los roles de los puntos medios a lo largo de los cuatro bordes y las esquinas del celosía [2] . Todos los gráficos autocomplementarios fuertemente regulares con menos de 37 vértices son gráficos de Paley. Sin embargo, hay grafos estrictamente regulares con 37, 41 y 49 vértices que no son grafos de Paley [3] .
El grafo de Rado es un grafo infinito autocomplementario.
Un grafo autocomplementario con n vértices tiene exactamente la mitad del número de aristas del grafo completo , es decir, n ( n − 1)/4 aristas, y (si hay más de un vértice) su diámetro debe ser 2 o 3 [ 1] . Dado que n ( n − 1) debe ser divisible por 4, n debe ser congruente con 0 o 1 módulo 4. Por ejemplo, un gráfico con 6 vértices no puede ser autocomplementario.
El problema de comprobar si dos grafos autocomplementarios son isomorfos y comprobar si un grafo dado es autocomplementario son equivalentes en tiempo de ejecución al problema general de isomorfismo de grafos [4] .