Комплемент графа

У теорији графова, комплемент или инверз графа је граф са истим скупом чворова, такав да су два чвора из суседна ако и само ако та два чвора нису суседна у графу . То јест, комплемент графа се добија тако што се додају све недостајуће гране, а уклоне оне које су већ биле у графу. Овде се не ради о комплементу скупа графа; само се гране комплементирају.

Петерсенов граф (лево), и његов комплемент (десно).

Формална конструкција

уреди

Ако је дат граф   са чворовима   и гранама  , његов комплемент  , се конструише на следећи начин:

  •   и
  • за клику   од   чворова, важи  .