Graf complementar
Fie G=(X,U) un graf neorientat.
Se numește graf complementar al lui G un graf G1=(X1,U1) cu proprietatea că X1 conține aceleași noduri (X1=X), iar U1 conține toate muchiile care nu aparțin lui U.
Pe scurt, graful complementar conține toate muchiile care nu apar în graful de referință (ne putem gândi la el ca fiind „graful opus”).
Un graf neorientat și complementarul său:
Toate (și doar) muchiile care nu apar în graful inițial apar în complementar.
Proprietățile grafului complementar
- Suma muchiilor unui graf neorientat și ale complementarului său este C2n (numărul maxim de muchii pentru un graf cu n noduri);
- Un graf neorientat are un singur graf complementar;
- Graful complet este graful cu toate muchiile posibile.Graful complet are complementar Graful nul este un graf fără muchii.graful nul (și invers).