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

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

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

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

Ако је дат граф $G(V_G, E_G)$ са чворовима $V_G$ и гранама $E_G$, његов комплемент $H(V_H, E_H)$, се конструише на следећи начин:

• $V_H = V_G$ и
• за клику $K^n(V_K, E_K)$ од $n = |V_G|$ чворова, важи $E_H = E_K \setminus E_G$.