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

Grafy ${\displaystyle G\ }$ a ${\displaystyle G_{0}\ }$ sa nazývajú komplementárne grafy.

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