Complementgraaf

De Petersen-graaf, links, met zijn complementgraaf

In de grafentheorie is de complementgraaf van een enkelvoudige graaf $G$, een enkelvoudige graaf $H$ met dezelfde knopen als $G$, die met een zijde verbonden zijn als en slechts als ze in $G$ niet met een zijde zijn verbonden.

De complementgraaf van een graaf $G$ wordt vaak aangeduid met ${\overline {G}}$.

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

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

$E({\overline {G}})$ = $\{\{v_{1},v_{2}\}|v_{1},v_{2}\in V(G)\wedge v_{1}\not =v_{2}\}\backslash 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 ledige graaf, die enkel bestaat uit knopen en die geen zijden heeft.