Zu einem Graphen ${\displaystyle {}G=(V,E)}$ nennt man den Graphen ${\displaystyle {}(V,{\mathfrak {P}}_{2}\,(V)\setminus E)}$ den komplementären Graphen (oder Komplementärgraph ). Er wird mit ${\displaystyle {}G^{c}}$ bezeichnet.