Grafo autocomplementario

Los grafos autocomplementarios más simples son el camino de 4 vértices y el ciclo de 5 vértices.

Todo grafo de Paley es autocomplementario.

[1]​ Todo grafo fuertemente regular y autocomplementario con menos de 37 vértices es un grafo de Paley; pero, hay grafos fuertemente regulares con 37, 41 y 49 vértices que no son grafos de Paley.

Un grafo autocomplementario de n vértices tiene exactamente la mitad de aristas que su grafo completo, en este caso, n(n − 1)/4 aristas, y (si tiene más de un vértice) debe tener diámetro 2 o 3.

Los grafos autocomplementarios son interesantes por su relación con el problema de isomorfismo de grafos: determinar si dos grafos autocomplementarios que son isomorfos y comprobar si un determinado grafo que es autocomplementario son a su vez polinómicamente equivalentes al problema general de isomorfismo de grafos.