Komplement grafu

Komplement grafu alebo doplnok grafu  je graf  pre ktorý platí:
 a pre každé dva rôzne vrcholy  platí  práve vtedy ak . Graf  je teda úplným grafom. 

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

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

Teória grafov