En selvkomplementær graf er en graf , der er isomorf i forhold til dens komplement . De enkleste ikke-trivielle selvkomplementære grafer er en 4-vertex- sti og en 5-vertex- cyklus .
Enhver Paley-graf er selvkomplementær [1] . For eksempel er en 3 × 3 tårngraf (Paley-graf af niende orden) også selvkomplementær på grund af symmetrien, der holder det centrale toppunkt på plads, men udveksler rollerne for midtpunkterne langs de fire kanter og hjørnerne af gitter [2] . Alle stærkt regulære selvkomplementære grafer med mindre end 37 hjørner er Paley-grafer. Der er dog strengt regulære grafer med 37, 41 og 49 hjørner, der ikke er Paley-grafer [3] .
Rado-grafen er en uendelig selvkomplementær graf.
En selvkomplementær graf med n toppunkter har nøjagtigt halvdelen af antallet af kanter af den komplette graf , dvs. n ( n − 1)/4 kanter, og (hvis der er mere end én toppunkter) skal dens diameter være enten 2 eller 3 [ 1] . Da n ( n − 1) skal være delelig med 4, skal n være kongruent med 0 eller 1 modulo 4. For eksempel kan en graf med 6 hjørner ikke være selvkomplementær.
Problemet med at kontrollere, om to selvkomplementære grafer er isomorfe, og at kontrollere, om en given graf er selvkomplementær, svarer i udførelsestid til det generelle grafisomorfiproblem [4] .