Definition: Complement Graph

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\}.\]

Example

The cycle graph \(C_5\) and its complement \(\overline C_5\).

complementgraph

(c) bookofproofs


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000