Complements and Complement Pairs

What a Graph Complement Records

A graph records which pairs of vertices are adjacent. Its complement records the other pairs: those that were not edges. This gives a useful way to describe a graph relative to the complete set of possible edges on its vertices. It also lets us compare graphs after relabeling: although the vertex names may change, the pattern of missing edges changes in a corresponding way.

Throughout, graphs are finite and simple, so they have no loops or multiple edges. In particular, an edge is an unordered pair of distinct vertices. If $G=(V,E)$, a nonedge of $G$ means an unordered pair of distinct vertices that is not in $E$. Nonedges are pairs of vertices, not additional edges of $G$.

Definition: The complement of $G=(V,E)$, denoted $\overline{G}$, is the simple graph with vertex set $V$ and edge set $$ E(\overline{G})=\{\{u,v\}:u,v\in V,\ u\ne v,\ \{u,v\}\notin E\}. $$ Thus $G$ and $\overline{G}$ have exactly the same vertices, and each pair of distinct vertices is an edge in exactly one of them.

When we write an edge as $uv$, the order of its endpoints does not matter: $uv$ and $vu$ name the same pair. There are no loops in either graph, so pairs such as $uu$ are never considered when forming the complement. The definition applies also when $V$ is empty or has one vertex; in either case there are no pairs of distinct vertices, and both edge sets are empty.

Basic Checks for a Complement

For a graph of order $n=|V|$, there are $\binom{n}{2}$ possible unordered pairs of distinct vertices. Each is either an edge of $G$ or an edge of $\overline{G}$, but not both. Consequently, if $m=|E(G)|$, then

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

There is also a check at each vertex. Among the other $n-1$ vertices, each is either adjacent to $v$ in $G$ or adjacent to $v$ in $\overline{G}$. These two groups do not overlap and together include all other vertices. Therefore

\deg_G(v)+\deg_{\overline{G}}(v)=n-1 \qquad\text{for every }v\in V.

Theorem: For every finite simple graph $G$, each pair of distinct vertices is an edge in exactly one of $G$ and $\overline{G}$. In particular, $\overline{\overline{G}}=G$, $|E(\overline{G})|=\binom{n}{2}-|E(G)|$, and $\deg_G(v)+\deg_{\overline{G}}(v)=n-1$ for every $v\in V$.

Proof. Fix any distinct vertices $u,v\in V$. If $uv\in E(G)$, the definition of $E(\overline{G})$ excludes $uv$ from that set. If $uv\notin E(G)$, the definition includes $uv$ in $E(\overline{G})$. These alternatives are exhaustive and mutually exclusive, proving the first assertion. Applying the same rule to $\overline{G}$ puts $uv$ in $\overline{\overline{G}}$ exactly when it is absent from $\overline{G}$, which happens exactly when $uv\in E(G)$. Both graphs have vertex set $V$, so they have the same vertices and edges; hence $\overline{\overline{G}}=G$. There are $\binom{n}{2}$ distinct pairs in total, and exactly $|E(G)|$ of them are edges of $G$, leaving $\binom{n}{2}-|E(G)|$ edges for the complement. Finally, for a fixed vertex $v$, each of the $n-1$ other vertices is a neighbor of $v$ in exactly one of the two graphs. Counting those neighbors gives the degree identity. If $n$ is $0$ or $1$, there are no pairs to count and the same conclusions hold. $\square$

Calculating Complements from Edge Lists

Worked Example: Listing Every Missing Pair

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,13,24,35\}$. Find $\overline{G}$ and check its edge and degree counts.

First list all unordered pairs of distinct vertices. There are $\binom{5}{2}=5\cdot4/2=10$ such pairs: $12,13,14,15,23,24,25,34,35,45$. Remove the four edges already in $E$, namely $12,13,24,35$. The remaining pairs are $14,15,23,25,34,45$, so $E(\overline{G})=\{14,15,23,25,34,45\}$.

The edge-count formula gives $|E(\overline{G})|=\binom{5}{2}-|E(G)|=10-4=6$, agreeing with the six listed complement edges. Check the degrees vertex by vertex. In $G$, the degrees of $1,2,3,4,5$ are respectively $2,2,2,1,1$. In $\overline{G}$, the listed edges give degrees $2,2,2,3,3$, respectively. The sums at the vertices are $2+2=4$, $2+2=4$, $2+2=4$, $1+3=4$, and $1+3=4$; each equals $5-1=4$.

Check: The original and complement edge lists are disjoint, and together they contain all ten distinct pairs. In particular, vertex $5$ has degree $1$ in $G$, since its only incident edge is $35$, and degree $3$ in $\overline{G}$, since its incident complement edges are $15,25,45$.

Worked Example: A Graph Isomorphic to Its Complement

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. Its complement has the remaining pairs: $E(\overline{G})=\{13,14,24\}$. We will give an explicit bijection showing that these two graphs are isomorphic.

Define $\phi:V(G)\to V(\overline{G})$ by $\phi(1)=3,\ \phi(2)=1,\ \phi(3)=4,\ \phi(4)=2$. The four images are distinct and comprise $\{1,2,3,4\}$, so $\phi$ is a bijection. The edges of $G$ map as follows: $12\mapsto31=13$, $23\mapsto14$, and $34\mapsto42=24$. These are exactly the three edges of $\overline{G}$.

For an additional check, the nonedges of $G$ are $13,14,24$. Their images are $34,23,12$, none of which is an edge of $\overline{G}$. Thus the bijection sends edges to edges and nonedges to nonedges. Therefore $G$ and $\overline{G}$ are isomorphic.

Check: $G$ has $3$ edges, and $\overline{G}$ has $\binom{4}{2}-3=6-3=3$ edges, as the lists show. This equality of edge counts is necessary here but is not, by itself, enough to prove the graphs are isomorphic; the explicit bijection supplies the required verification.

Complementation and Isomorphism

An isomorphism is a bijection between vertex sets that preserves adjacency in both directions. Equivalently, for every pair of distinct vertices $u,v$, the pair $uv$ is an edge in the first graph exactly when the pair of image vertices is an edge in the second. The “both directions” condition matters: an isomorphism preserves nonedges as well as edges.

Theorem: If finite simple graphs $G$ and $H$ are isomorphic, then $\overline{G}$ and $\overline{H}$ are isomorphic. More generally, $G$ is isomorphic to $H$ if and only if $\overline{G}$ is isomorphic to $\overline{H}$.

Proof. First suppose $f:V(G)\to V(H)$ is an isomorphism. It is a bijection, so it also gives a bijection from $V(\overline{G})$ to $V(\overline{H})$, since these vertex sets are the original vertex sets. Take any distinct $u,v\in V(G)$. By the definition of complement, $uv\in E(\overline{G})$ exactly when $uv\notin E(G)$. Since $f$ is an isomorphism, $uv\notin E(G)$ exactly when $f(u)f(v)\notin E(H)$. By the complement definition again, this holds exactly when $f(u)f(v)\in E(\overline{H})$. Thus $f$ preserves adjacency in both directions for the complements, so it is an isomorphism from $\overline{G}$ to $\overline{H}$.

This proves the forward implication. For the reverse implication, suppose $\overline{G}$ is isomorphic to $\overline{H}$. Apply the forward implication just proved to these two graphs. Their complements are isomorphic, and the double-complement identity gives $\overline{\overline{G}}=G$ and $\overline{\overline{H}}=H$. Hence $G$ is isomorphic to $H$. $\square$

The theorem says that complementation depends only on the adjacency pattern, not on the names assigned to vertices. It also gives a useful way to compare two graphs: an explicit isomorphism between them automatically works between their complements. Conversely, an isomorphism between the complements implies one between the original graphs.

Worked Example: Complementing a Pair of Disjoint Edges

Let $G=(V,E)$ have $V=\{a,b,c,d\}$ and $E=\{ab,cd\}$. The six possible pairs are $ab,ac,ad,bc,bd,cd$. Removing $ab$ and $cd$ gives $E(\overline{G})=\{ac,ad,bc,bd\}$.

There are $|E(G)|=2$ edges in $G$, and the formula gives $|E(\overline{G})|=\binom{4}{2}-2=6-2=4$, matching the four listed edges. Each vertex has degree $1$ in $G$. In the complement, $a$ is incident with $ac,ad$, $b$ with $bc,bd$, $c$ with $ac,bc$, and $d$ with $ad,bd$, so each complement degree is $2$. For every vertex the degree sum is $1+2=3=4-1$.

Taking the complement again removes $ac,ad,bc,bd$ from the six possible pairs, leaving $ab,cd$. Thus the result is exactly $G$, confirming the double-complement rule directly in this example.

Common Pitfalls and Why Complement Pairs Matter

A frequent error is to keep the original edges and add the missing ones. That produces a graph with too many edges, not the complement. In the first worked example, adding the original four edges to the six missing pairs would give all ten possible pairs. The correction is to use only the pairs absent from $E(G)$; the edge sets of a graph and its complement must be disjoint.

Another error is to include loops or count an unordered pair twice. For a vertex set of size $n$, the number of possible edges is $\binom{n}{2}$, not $n^2$: each edge uses two distinct vertices, and the pairs $uv$ and $vu$ are the same edge. The degree check is also vertex-specific. It must use the actual neighbors in each edge list, not just the total number of edges.

Complementation is useful because it turns a question about present edges into a question about absent edges. The identities above provide quick consistency tests: the two edge counts add to $\binom{n}{2}$, and the two degrees at each vertex add to $n-1$. The isomorphism theorem means that structural comparisons made after complementation remain independent of vertex labels. These checks do not replace an explicit isomorphism when one is required, but they can reveal an incorrect edge list or rule out an isomorphism when a necessary count disagrees.

Check Your Understanding

Use the definition and the two counting checks to answer each question.

Let $V=\{1,2,3,4\}$ and $E=\{12,14,23\}$. List $E(\overline{G})$, then verify the edge count.
For a graph of order $n$, explain why $\deg_G(v)+\deg_{\overline{G}}(v)=n-1$ also holds when $n=1$.
Prove directly from the definition that no pair of distinct vertices is an edge of both $G$ and $\overline{G}$.
If $G$ and $H$ are isomorphic, explain why an isomorphism from $G$ to $H$ also preserves nonedges.
A graph on six vertices has seven edges. How many edges does its complement have? State the count of possible pairs used in your calculation.