Isetäienduv graaf

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

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

Ü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äisgraafi 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.