A KOMPLEMENTER GRÁF FOGALMA
Az 1a. feladat esetében azt a gráfot tekintettük, amelyben a pontok az emberek, és két pontot akkor kötünk össze éllel, ha a nekik megfelelő emberek ismerik egymást. A 3a feladatban és a „kézfogós” feladatnál viszont azt a gráfot tekintettük, amelyben két pontot akkor kötünk össze éllel, ha a nekik megfelelő emberek nem ismerik egymást. Ez a két gráf egymás komplementere.
A G gráf komplementere az a gráf, amelynek pontjai megegyeznek G pontjaival, és amelyben két pont pontosan akkor van összekötve éllel, ha G-ben nincs összekötve.
Legyen például a G gráf egy háromszög, azaz legyen olyan hárompontú gráf, amelyben bármely két pont között fut él. Ekkor G komplementere a hárompontú üres gráf. Általában is igaz, hogy ha Kn-nel jelöljük az n pontú teljes gráfot, azaz azt az n pontú gráfot, amelyben bármely két pontot él köt össze, akkor Kn komplementere az n pontú üres gráf, tehát az az n pontú gráf, amelyben egyetlen él sincs behúzva.
Ha G négypontú, és pontjai A,B,C,D, és élei egy „kört” alkotnak, vagyis élei AB,BC,CD,DA, akkor a komplementer gráf az a négypontú gráf, amelynek két éle AC és BD.