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.