Isetäienduv graaf

Isetäinduv graaf (sinine) on isomorfne oma täiendiga (punane).

Isetäienduv graaf on graaf mis on isomorfne tema täiendiga. Üks lihtsaimad mittetriviaalsed isetäienduvad on ka 5-tipuline 5-vöö-regulaarne graaf.

Ühe isetäienduvate graafide klassi moodustavad bisümmeetrilised Paley graafid. Iga Paley graaf on tugevregulaarne. Kõik tugevregulaarsed, vähem kui 37 tipuga graafid on Paley graafid.

Iga n-tipulise isetäienduva graafi servade arv on parajasti pool vastava täigraafi servade arvust, st n(n − 1)/4 serva, ja (kui servade arv on suurem kui 1) peab selle diameeter olema 2 või 3. Seega n(n −1) peab jaguma 4-ga, n peab olema kongruentne väärtustega 0 või 1 mod 4, mis tähendab et näiteks 6-tipuline graaf ei saa olla isetäienduv.