Tags: #definition

complement of a graph

Let $G=(V,E)$ be a simple graph. Its complement is the graph $\overline{G}=(V,\overline{E})$ where $\overline{E}$ is defined as follows:
There is an edge $(v,v^{\prime })$ if and only if $(v,v^{\prime })\notin E$.