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} \isin 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.