Given a simple undirected graph \(G(V,E)\), the complement graph is the graph \(\overline G(V,\overline E)\) obtained by taking the vertices of \(G\) and joining two of them whenever they are not joined in \(G\), formally
\[\overline E:=\{xy:\,x\neq y\text{ and }xy\not\in E\}.\]
The cycle graph \(C_5\) and its complement \(\overline C_5\).
(c) bookofproofs
