# Chapter 13. Complement Graphs # Chapter 13. Complement Graphs The complement of a graph records the missing edges of the graph. It keeps the same vertices, removes the existing edges, and adds exactly those edges that were absent before. Complementation is defined most naturally for simple graphs. If loops and multiple edges are allowed, extra conventions are needed. In this chapter, all graphs are finite simple undirected graphs unless stated otherwise. ## 13.1 Definition Let $$ G=(V,E) $$ be a simple graph. The **complement** of \(G\), written $$ \overline{G}, $$ is the graph with the same vertex set as \(G\), where two distinct vertices are adjacent in \(\overline{G}\) exactly when they are not adjacent in \(G\). This is the standard definition of graph complementation. Thus $$ V(\overline{G})=V(G). $$ For distinct vertices \(u,v \in V(G)\), $$ \{u,v\}\in E(\overline{G}) $$ if and only if $$ \{u,v\}\notin E(G). $$ Equivalently, the edge set of \(\overline{G}\) is $$ E(\overline{G}) = \{\{u,v\}:u,v\in V,\ u\ne v,\ \{u,v\}\notin E(G)\}. $$ The complement exchanges adjacency and non-adjacency. ## 13.2 Complement Relative to a Complete Graph For a simple graph on \(n\) vertices, the complete graph \(K_n\) contains every possible edge. The complement of \(G\) is obtained from \(K_n\) by removing the edges of \(G\): $$ E(\overline{G}) = E(K_n) \setminus E(G). $$ This formula is often the cleanest way to think about complements. The graph \(G\) and its complement together fill the complete graph: $$ E(G) \cup E(\overline{G}) = E(K_n), $$ and $$ E(G) \cap E(\overline{G}) = \varnothing. $$ Thus \(G\) and \(\overline{G}\) split all possible edges between the same vertex set. ## 13.3 Number of Edges A simple graph on \(n\) vertices can have at most $$ \binom{n}{2}=\frac{n(n-1)}{2} $$ edges. If \(G\) has \(m\) edges, then its complement has $$ \binom{n}{2}-m $$ edges. This follows because every possible edge belongs to exactly one of \(G\) or \(\overline{G}\). For example, if \(G\) has \(6\) vertices and \(7\) edges, then $$ |E(\overline{G})| = \binom{6}{2}-7 = 15-7 = 8. $$ Complementation turns sparse graphs into dense graphs and dense graphs into sparse graphs. ## 13.4 Degree in the Complement Let \(G\) be a simple graph of order \(n\). For any vertex \(v\), $$ \deg_{\overline{G}}(v) = n-1-\deg_G(v). $$ There are \(n-1\) possible neighbors of \(v\). Each one is either adjacent to \(v\) in \(G\) or adjacent to \(v\) in \(\overline{G}\), but not both. Thus the degree sequence of the complement can be computed directly from the degree sequence of \(G\). If \(G\) has degree sequence $$ (d_1,d_2,\ldots,d_n), $$ then \(\overline{G}\) has degrees $$ (n-1-d_1,\ n-1-d_2,\ \ldots,\ n-1-d_n), $$ then sorted if one wants the usual nonincreasing degree sequence. ## 13.5 Examples If \(G\) is the empty graph on \(n\) vertices, then no pair of distinct vertices is adjacent in \(G\). Therefore every pair is adjacent in \(\overline{G}\). Hence $$ \overline{G}=K_n. $$ If \(G=K_n\), then every possible edge is already present. Therefore no edge remains for the complement, so $$ \overline{K_n} $$ is the empty graph on \(n\) vertices. These two examples are standard consequences of the definition. For a path \(P_4\) with vertices $$ 1,2,3,4 $$ and edges $$ \{1,2\},\{2,3\},\{3,4\}, $$ the possible edges in \(K_4\) are $$ \{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}. $$ Removing the path edges leaves $$ E(\overline{P_4}) = \{\{1,3\},\{1,4\},\{2,4\}\}. $$ Thus \(\overline{P_4}\) is also a path on four vertices, with vertex order $$ 3,1,4,2. $$ ## 13.6 Complement of a Cycle Let \(C_n\) be the cycle graph on \(n\) vertices. Each vertex in \(C_n\) has degree \(2\). Therefore each vertex in the complement has degree $$ n-1-2=n-3. $$ So $$ \overline{C_n} $$ is \((n-3)\)-regular. For example, \(C_5\) is a cycle on five vertices. Its complement is also a cycle on five vertices: $$ \overline{C_5}\cong C_5. $$ This is one of the simplest examples of a self-complementary graph. ## 13.7 Complement and Isomorphism Complementation respects graph isomorphism. If $$ G \cong H, $$ then $$ \overline{G} \cong \overline{H}. $$ ### Proof Let $$ f:V(G)\to V(H) $$ be an isomorphism. Then for distinct vertices \(u,v\), $$ \{u,v\}\in E(G) $$ if and only if $$ \{f(u),f(v)\}\in E(H). $$ Taking negations gives $$ \{u,v\}\notin E(G) $$ if and only if $$ \{f(u),f(v)\}\notin E(H). $$ Therefore $$ \{u,v\}\in E(\overline{G}) $$ if and only if $$ \{f(u),f(v)\}\in E(\overline{H}). $$ So the same bijection \(f\) is an isomorphism from \(\overline{G}\) to \(\overline{H}\). ## 13.8 Double Complement The complement of the complement is the original graph: $$ \overline{\overline{G}}=G. $$ This follows directly from the definition. A pair of distinct vertices is adjacent in \(\overline{\overline{G}}\) exactly when it is not adjacent in \(\overline{G}\), which means it is adjacent in \(G\). Thus complementation is an involution: applying it twice returns to the starting graph. ## 13.9 Complement and Induced Subgraphs Complementation commutes with taking induced subgraphs. If $$ S\subseteq V(G), $$ then $$ \overline{G[S]} = \overline{G}[S]. $$ On the left, one first takes the subgraph induced by \(S\), then complements it. On the right, one first complements \(G\), then takes the induced subgraph on \(S\). Both graphs have vertex set \(S\). Two distinct vertices in \(S\) are adjacent in either graph exactly when they are not adjacent in \(G\). This relationship is a standard property of graph complements. This property is useful in clique theory, independent sets, and hereditary graph classes. ## 13.10 Cliques and Independent Sets A **clique** in \(G\) is a set of vertices that are pairwise adjacent. An **independent set** in \(G\) is a set of vertices that are pairwise non-adjacent. Complementation exchanges these two notions. A set \(S\subseteq V(G)\) is a clique in \(G\) if and only if \(S\) is an independent set in \(\overline{G}\). Similarly, \(S\) is an independent set in \(G\) if and only if \(S\) is a clique in \(\overline{G}\). This clique-independent-set duality is a basic application of graph complementation. Thus questions about cliques can often be translated into questions about independent sets in the complement. ## 13.11 Chromatic Number and Clique Cover The chromatic number of a graph \(G\), written $$ \chi(G), $$ is the minimum number of colors needed to color the vertices so that adjacent vertices receive different colors. A proper coloring of \(G\) partitions \(V(G)\) into independent sets. Since independent sets in \(G\) are cliques in \(\overline{G}\), a coloring of \(G\) corresponds to a partition of \(V(\overline{G})\) into cliques. Thus the chromatic number of \(G\) can be interpreted as the minimum number of cliques needed to cover the vertices of \(\overline{G}\). This is another example of complement duality: coloring problems become clique-cover problems. ## 13.12 Connectivity and Complements Connectivity behaves differently under complementation. A disconnected graph may have a connected complement. In fact, if \(G\) is disconnected and has at least two components, then \(\overline{G}\) is connected. ### Proof Let \(u\) and \(v\) be distinct vertices. If \(u\) and \(v\) lie in different components of \(G\), then they are not adjacent in \(G\), so they are adjacent in \(\overline{G}\). If \(u\) and \(v\) lie in the same component of \(G\), choose a vertex \(w\) in a different component. Then \(u\) is adjacent to \(w\) in \(\overline{G}\), and \(w\) is adjacent to \(v\) in \(\overline{G}\). Therefore there is a path $$ u,w,v $$ in \(\overline{G}\). Hence any two vertices are connected in \(\overline{G}\). The converse is false. A connected graph may also have a connected complement. For example, \(P_4\) and \(\overline{P_4}\) are both connected. ## 13.13 Complement and Adjacency Matrices Let \(G\) be a simple graph of order \(n\), and let \(A\) be its adjacency matrix. Let \(J\) be the \(n\times n\) all-ones matrix, and let \(I\) be the identity matrix. The adjacency matrix of the complement is $$ A(\overline{G}) = J-I-A(G). $$ The matrix \(J-I\) is the adjacency matrix of \(K_n\). It has \(1\) in every off-diagonal position and \(0\) on the diagonal. Subtracting \(A(G)\) removes precisely the edges already present in \(G\). This matrix formula is a standard expression of graph complementation. This formula connects graph complementation with algebraic graph theory. ## 13.14 Self-Complementary Graphs A graph is **self-complementary** if it is isomorphic to its complement: $$ G \cong \overline{G}. $$ This does not usually mean that $$ G=\overline{G} $$ with the same labels. It means the two graphs have the same structure after relabeling. Examples include \(P_4\) and \(C_5\). If \(G\) is self-complementary with \(n\) vertices and \(m\) edges, then $$ m = \binom{n}{2}-m. $$ Therefore $$ 2m=\binom{n}{2} $$ and $$ m=\frac{n(n-1)}{4}. $$ Hence $$ n(n-1) $$ must be divisible by \(4\). This implies $$ n\equiv 0 \pmod 4 $$ or $$ n\equiv 1 \pmod 4. $$ So a self-complementary graph can have order only congruent to \(0\) or \(1\) modulo \(4\). ## 13.15 Complements of Special Graphs Several complements are immediate from the definition. | Graph \(G\) | Complement \(\overline{G}\) | |---|---| | Empty graph on \(n\) vertices | \(K_n\) | | \(K_n\) | Empty graph on \(n\) vertices | | \(P_4\) | Isomorphic to \(P_4\) | | \(C_5\) | Isomorphic to \(C_5\) | | \(C_n\) | \((n-3)\)-regular graph | | Complete bipartite graph \(K_{m,n}\) | Disjoint union \(K_m \cup K_n\) | For the last row, \(K_{m,n}\) has all edges between the two parts and no edges inside either part. Its complement has no edges between the parts, but it has all edges inside each part. Therefore $$ \overline{K_{m,n}} = K_m \cup K_n. $$ ## 13.16 Complement and Density The density of a simple graph on \(n\) vertices is often measured by $$ \frac{|E(G)|}{\binom{n}{2}}. $$ If \(G\) has density \(p\), then \(\overline{G}\) has density $$ 1-p. $$ Thus complementing a graph exchanges dense and sparse structure. This can be useful in proofs. If a graph has many missing edges, its complement has many edges. Sometimes it is easier to reason about the complement than about the original graph. ## 13.17 Algorithmic Considerations Explicitly constructing a complement may be expensive. If \(G\) is sparse, then \(\overline{G}\) may be dense. A graph with \(n\) vertices and only \(O(n)\) edges may have a complement with $$ \Theta(n^2) $$ edges. Therefore algorithms sometimes work with complements implicitly rather than materializing every missing edge. This distinction matters for large graphs because the complement can require much more memory than the original graph. Algorithmic work on complement graphs often studies traversal and connectivity without explicitly constructing the dense complement. ## 13.18 Example Let $$ V=\{a,b,c,d,e\} $$ and $$ E(G)= \{\{a,b\},\{a,c\},\{b,c\},\{d,e\}\}. $$ The complete graph on this vertex set has $$ \binom{5}{2}=10 $$ edges. The possible edges are $$ \{a,b\},\{a,c\},\{a,d\},\{a,e\}, \{b,c\},\{b,d\},\{b,e\}, \{c,d\},\{c,e\},\{d,e\}. $$ Removing the four edges of \(G\), we get $$ E(\overline{G})= \{\{a,d\},\{a,e\},\{b,d\},\{b,e\},\{c,d\},\{c,e\}\}. $$ Thus \(\overline{G}\) is the complete bipartite graph $$ K_{3,2} $$ with parts $$ \{a,b,c\} $$ and $$ \{d,e\}. $$ This example shows how a graph made from a triangle and an edge can have a highly connected complement across the two parts. ## 13.19 Summary The complement of a simple graph keeps the same vertex set and replaces edges by non-edges. If \(G\) has \(n\) vertices and \(m\) edges, then $$ |\overline{E}|=\binom{n}{2}-m. $$ For each vertex, $$ \deg_{\overline{G}}(v)=n-1-\deg_G(v). $$ Complementation is an involution: $$ \overline{\overline{G}}=G. $$ It exchanges cliques and independent sets, turns complete graphs into empty graphs, and often changes sparse graphs into dense graphs. Complement graphs are useful because they let one restate adjacency problems as non-adjacency problems and translate several graph properties into dual forms.