Komplementer gráf

A Petersen-gráf a bal oldalon és komplementere a jobb oldalon

Valamely $G=(V,E)$ gráf komplementer gráfja az a gráf, amelynek csúcshalmaza megegyezik a G gráf csúcshalmazával, az élhalmaza pedig a G gráf élhalmazának a komplementer halmaza (a teljes gráf élhalmazára, mint alaphalmazra nézve).

Definíció

A $G=(V,E)$ gráf komplementere a $\overline{G}:=(V,F)$ gráf, ha tetszőleges $u, v \in V$ csúcsokra fennáll, hogy $\big\{ u,v \big\} \in E \Leftrightarrow \big\{ u,v \big\} \not \in F$

Elemi tulajdonságok

Egyszerű megfontolásokkal adódnak az alábbi összefüggések a komplementer gráf fokszámaira:

$deg_{\overline{G}}(u) = |V| - 1 - deg_{G}(u)$

illetve az élek számosságára:

$|F|={|V|^2 - |V| \over 2}-|E|$