En självkomplementär graf är en graf som är isomorf till dess komplement . De enklaste icke-triviala självkomplementära graferna är en 4-vertex- bana och en 5-vertex- cykel .
Alla Paley-grafer är självkomplementerande [1] . Till exempel är en 3 × 3 torngraf (Paley-graf av nionde ordningen) också självkomplementär på grund av symmetrin som håller den centrala vertexen på plats, men byter ut rollerna för mittpunkterna längs de fyra kanterna och hörnen på galler [2] . Alla starkt regelbundna självkomplementerande grafer med mindre än 37 hörn är Paley-grafer. Det finns dock strikt regelbundna grafer med 37, 41 och 49 hörn som inte är Paley-grafer [3] .
Rado-grafen är en oändlig självkompletterande graf.
En självkomplementär graf med n hörn har exakt hälften av antalet kanter av hela grafen , dvs. n ( n − 1)/4 kanter, och (om det finns mer än en hörn) måste dess diameter vara antingen 2 eller 3 [ 1] . Eftersom n ( n − 1) måste vara delbart med 4 måste n vara kongruent med 0 eller 1 modulo 4. Till exempel kan en graf med 6 hörn inte vara självkomplementär.
Problemet med att kontrollera om två självkomplementära grafer är isomorfa och att kontrollera om en given graf är självkomplementär är likvärdiga i exekveringstid med det allmänna grafisomorfismproblemet [4] .