Komplement grafu

Petersenov graf (vľavo) a jeho komplement (vpravo)

Komplement grafu alebo doplnok grafu $G$ je graf $G_0$ pre ktorý platí: $V=V_0$ a pre každé dva rôzne vrcholy $u,v$ platí $u,v\in E$ práve vtedy ak $u,v\notin E_0$. Graf $G_1=(V,E\cup E_0)$ je teda úplným grafom.

Grafy $G$ a $G_0$ sa nazývajú komplementárne grafy.

Vlastnosti

• Komplement úplného grafu je graf bez hrán.
• Komplement triviálneho grafu je triviálny graf.