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

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

У теорији графова, комплемент или инверз графа $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}$.