En komplementgraf är inom matematik, specifikt grafteori, en graf som konstrueras utifrån en given graf G genom att låta graferna ha samma nodmängd, men att två noder i komplementgrafen har en båge mellan sig om och endast om de inte har en båge mellan sig i G.

Om ${\displaystyle G=(N,B)}$ är en graf och K består av alla delmängder av N med två element så är komplementgrafen till G:

${\displaystyle {\overline {G))=(N,B\setminus K).}$

Observera att en komplementgraf inte är detsamma som ett mängdteoretiskt komplement.

Flera grafteoretiska koncept är varandras motsatser sett i komplementgrafer. En bågfri grafs komplementgraf är en komplett graf, en oberoende mängd i en graf blir en klick i dess komplementgraf, en triangelfri graf blir en klofri graf.

• Eriksson, Kimmo; Hillevi Gavel (2002). Diskret matematik och diskreta modeller. Studentlitteratur. ISBN 91-44-02465-7 
• Bollobás, Béla (2002). Modern Graph Theory. Springer Verlag. ISBN 978-0387984889