Exercise 469Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

The complement of a graph

#complement#graph#edges

Statement

Let $G$ have $n$ vertices and $m$ edges. Describe the complement $\overline{G}$ and compute its number of edges.

Hint

Two vertices are adjacent in $\overline{G}$ iff they are not adjacent in $G$ .

Show solutionHide solution

Definition. $V(\overline{G})=V(G)$ ; edges of $\overline{G}$ = non-edges of $G$ .

Edge count. Total possible edges: $\binom{n}{2}$ . Non-edges of $G$ : $\binom{n}{2}-m$ .

Degree. $\deg_{\overline{G}}(v)=n-1-\deg_G(v)$ .

Conclusion. $|E(\overline{G})|=\binom{n}{2}-m$ .