Un graf auto-complementar este un graf izomorf cu complementul său . Cele mai simple grafice auto-complementare non-triviale sunt o cale cu 4 vârfuri și un ciclu cu 5 vârfuri .
Orice graf Paley este auto-complementar [1] . De exemplu, un grafic 3 × 3 rook (graficul Paley de ordinul al nouălea) este, de asemenea, autocomplementar datorită simetriei care menține vârful central pe loc, dar schimbă rolurile punctelor mijlocii de-a lungul celor patru margini și colțurilor zăbrele [2] . Toate graficele auto-complementare puternic obișnuite cu mai puțin de 37 de vârfuri sunt grafice Paley. Totuși, există grafice strict regulate cu 37, 41 și 49 de vârfuri care nu sunt grafice Paley [3] .
Graficul Rado este un graf infinit auto-complementar.
Un graf autocomplementar cu n vârfuri are exact jumătate din numărul de muchii ale graficului complet , adică n ( n − 1)/4 muchii, iar (dacă există mai multe vârfuri) diametrul său trebuie să fie 2 sau 3 [ 1] . Deoarece n ( n − 1) trebuie să fie divizibil cu 4, n trebuie să fie congruent cu 0 sau 1 modulo 4. De exemplu, un grafic cu 6 vârfuri nu poate fi autocomplementar.
Problema verificării dacă două grafuri autocomplementare sunt izomorfe și a verificării dacă un graf dat este auto-complementar sunt echivalente în timpul de execuție cu problema generală a izomorfismului grafului [4] .