In de grafentheorie is de complementgraaf van een enkelvoudige graaf ${\displaystyle G}$ een enkelvoudige graaf ${\displaystyle H}$ met dezelfde knopen als ${\displaystyle G}$, waarin twee knopen door een zijde verbonden worden dan en slechts dan als die twee knopen in de oorspronkelijke graaf ${\displaystyle G}$ niet door een zijde verbonden worden. De complementgraaf van een graaf ${\displaystyle G}$ wordt vaak aangeduid met ${\displaystyle {\overline {G}}}$.

De complementgraaf ${\displaystyle {\overline {G}}}$ van ${\displaystyle G=(V(G),E(G))}$ met knopen ${\displaystyle V(G)}$ en zijden ${\displaystyle E(G)}$ is de graaf gegeven door het paar ${\displaystyle (V({\overline {G}})}$, ${\displaystyle E({\overline {G}}))}$ waarvoor geldt:

${\displaystyle V({\overline {G}})=V(G)}$

${\displaystyle E({\overline {G}})}$ = ${\displaystyle \{\{v_{1},v_{2}\}\mid v_{1},v_{2}\in V(G)\wedge v_{1}\not =v_{2}\}\setminus E(G)}$

De complementgraaf van een complementgraaf is de oorspronkelijke graaf. Een graaf die isomorf is met zijn complementgraaf noemt men zelf-complementair. De complementgraaf van een volledige graaf is een lege graaf, die alleen uit knopen bestaat en geen zijden heeft. Een clique in een graaf ${\displaystyle G}$ induceert een onafhankelijke verzameling in de complementaire graaf ${\displaystyle {\overline {G}}}$ ervan.