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 aceleași noduri și toate muchiile care nu apar în graful inițial (ne putem gândi la el ca fiind „graful opus”).

Graf neorientat + Graful complementar

  Graful complementar conține toate muchiile care nu apar în graful inițial. Dacă adunăm numărul de muchii ale ambelor grafuri, obținem C2n     (numărul maxim de muchii pentru n noduri).

Un graf neorientat G are un singur graf complementar.