Complement graph
In graph theory, the complement of a simple undirected graph G = (V, E), often denoted \overline{G} or G^c, is the graph with the same vertex set V in which two distinct vertices are adjacent if and only if they are not adjacent in G.[1] The edge set of \overline{G} thus consists of all possible edges on V excluding those in E, making the union of G and \overline{G} the complete graph K_{|V|}.[2] If G has n = |V| vertices and m = |E| edges, then \overline{G} has \binom{n}{2} - m edges, and the degree of each vertex v in \overline{G} is n - 1 - \deg_G(v).[1] A notable class of graphs related to complements are self-complementary graphs, which are isomorphic to their own complements.[3] Such graphs must have exactly n(n-1)/4 edges, implying that self-complementary graphs on n vertices exist only when n \equiv 0 or $1 \pmod{4}.[4] Examples include the path graph P_4 on 4 vertices and the cycle graph C_5 on 5 vertices, both of which are self-complementary.[4] Self-complementary graphs are always connected and have diameters of 2 or 3.[4] Complements play a key role in studying structural properties of graphs, particularly in relating cliques and independent sets: a clique of size k in G corresponds exactly to an independent set of size k in \overline{G}, and vice versa.[5] This duality simplifies algorithms and proofs for problems like finding maximum cliques or independent sets by transforming one into the other via the complement.[6] In extremal graph theory, complements are used in Ramsey theory, where the Ramsey number R(k, l) is the smallest n such that every graph on n vertices contains a clique of size k or an independent set of size l (equivalently, a clique of size l in the complement).[7] Additionally, the complement of an empty graph (no edges) is the complete graph K_n, and vice versa, highlighting their foundational symmetry in graph constructions.[1]Fundamentals
Definition
In graph theory, the complement of a simple undirected graph G = (V, E), where V is the vertex set and E is the edge set consisting of unordered pairs of distinct vertices with no loops or multiple edges, is the graph \overline{G} = (V, \overline{E}) on the same vertex set, whose edge set \overline{E} consists of all possible unordered pairs of distinct vertices from V that are not in E.[8][2] Formally, \overline{E} = \bigl\{ \{u,v\} \subseteq V \mid u \neq v, \, \{u,v\} \notin E \bigr\}. This construction assumes G is simple, meaning it has no self-loops and no multiple edges between the same pair of vertices.[8] The adjacency matrix provides a matrix representation of the complement. If A is the adjacency matrix of G, with A_{ij} = 1 if \{i,j\} \in E and $0 otherwise (and A_{ii} = 0), then the adjacency matrix of \overline{G} is J - I - A, where J is the all-ones matrix of the same order and I is the identity matrix.[9][10] This concept extends to directed graphs. For a simple directed graph G = (V, E) without self-loops, where edges are ordered pairs of distinct vertices, the complement \overline{G} = (V, \overline{E}) has an arc from u to v (with u \neq v) if and only if there is no such arc in G, so \overline{E} is the set of all possible directed edges between distinct vertices minus E.[11] The complement of any graph G on n = |V| vertices relates to the complete graph K_n, which has all possible edges, as \overline{G} consists precisely of the edges absent in G.[8]Basic Properties
The complement of a simple graph G with vertex set V and order n = |V| preserves the vertex set, so the complement \overline{G} has exactly n vertices.[7] Complementation reverses adjacency relations while maintaining the symmetry of non-adjacency, as two vertices are adjacent in \overline{G} precisely when they are non-adjacent in G.[1] A key structural consequence is the relationship between vertex degrees in G and \overline{G}. For any vertex v \in V with degree d_G(v) in G, the degree of v in \overline{G} is d_{\overline{G}}(v) = n - 1 - d_G(v), since v connects to all other vertices except itself and its neighbors in G.[7] The edge count in \overline{G} follows directly from the total possible edges in the complete graph on n vertices. If G has m edges, then \overline{G} has \binom{n}{2} - m = \frac{n(n-1)}{2} - m edges.[7] The union of G and \overline{G} forms the complete graph K_n, as every pair of distinct vertices is adjacent in exactly one of the two graphs.[1]Examples and Applications
Illustrative Examples
The complement of the empty graph on n vertices, which contains no edges between its vertices, is the complete graph K_n, in which every pair of distinct vertices is adjacent.[12] Conversely, the complement of the complete graph K_n is the empty graph on n vertices.[12] A simple illustration arises with three vertices forming the complete graph K_3, known as a triangle where each vertex connects to the other two. The complement of this graph consists of the same three vertices with no edges between them, resulting in three isolated vertices. To visualize, label the vertices A, B, and C: in K_3, the edges are AB, AC, and BC; in the complement, there are no edges at all. The path graph P_4 on four vertices, arranged linearly as A-B-C-D with edges AB, BC, and CD, provides another clear example. Its complement is isomorphic to P_4 itself, serving as a basic self-complementary graph where the structure mirrors its own complement under vertex relabeling.[13][12] Similarly, the cycle graph C_5 on five vertices, forming a pentagon with edges connecting them in a closed loop (e.g., 1-2-3-4-5-1), has a complement that is also isomorphic to C_5. This highlights how certain odd-length cycles exhibit self-complementarity.[14] These examples demonstrate that complements of regular graphs are also regular, as seen in the consistent degrees preserved in structures like C_5, which is 2-regular and whose complement maintains the same degree sequence.[12]Theoretical Applications
Complement graphs provide a powerful duality in graph theory, particularly in relating independent sets and cliques. An independent set in a graph G corresponds exactly to a clique in its complement \overline{G}, and vice versa, because the absence of edges within the set in G implies the presence of all possible edges in \overline{G}. This duality implies that the size of the maximum independent set \alpha(G) in G equals the clique number \omega(\overline{G}) of the complement. Such relationships facilitate the transfer of algorithmic and structural insights between the two problems, enabling researchers to solve one by transforming it into the other. In extremal graph theory, complements reveal structural equivalences between graph classes. For instance, the complement of a triangle-free graph (one without K_3 subgraphs) is claw-free, meaning it contains no induced K_{1,3} (a star with three leaves).[15] This property arises because any potential claw in the complement would correspond to a triangle in the original graph, which is forbidden. Claw-free graphs, including these complements, have been extensively studied for their decomposition properties and algorithmic tractability in optimization problems.[16] Complement graphs play a key role in Ramsey theory by allowing analysis of edge distributions to bound Ramsey numbers. Ramsey numbers R(s,t) denote the smallest order of a graph where any 2-coloring of the edges forces either a clique of size s or an independent set of size t; considering the complement shifts the perspective from cliques in one coloring to independent sets in the other, aiding in lower bound constructions through self-complementary graphs or balanced incomplete block designs.[17] For example, self-complementary graphs like the 5-cycle provide tight examples for R(3,3)=6, as neither the graph nor its complement contains a triangle.[17] The concept of complementation is integral to the characterization of perfect graphs. According to the Strong Perfect Graph Theorem, a graph is perfect if and only if neither it nor its complement contains an induced odd cycle of length at least five (an odd hole or odd antihole).[18] This theorem, proved by Chudnovsky, Robertson, Seymour, and Thomas, underscores how complements help identify forbidden subgraphs that disrupt perfectness, linking chromatic and clique numbers across induced subgraphs.[18] In network analysis, complement graphs model non-interactions or absences of relationships, offering insights into social and biological systems. In social networks, where edges represent friendships or collaborations, the complement captures enmities or non-connections, facilitating community detection by partitioning based on dense non-edge clusters.[19] Similarly, in biological networks like protein-protein interactions, complements highlight potential inhibitory or non-binding pairs, aiding in the inference of regulatory mechanisms and pathway disruptions.[20] This approach enhances modularity optimization and anomaly detection in sparse interaction data.[19]Self-Complementary Graphs
Definition and Characterization
A self-complementary graph is an undirected simple graph G = (V, E) that is isomorphic to its complement \overline{G} = (V, \overline{E}), where \overline{E} consists of all possible edges between vertices in V that are absent from E.[21] This isomorphism implies that G and \overline{G} share identical structural properties, such as the same degree sequence and connectivity characteristics.[4] For a graph on n vertices to be self-complementary, n must satisfy n \equiv 0 or $1 \pmod{4}, as this ensures the total number of edges in the complete graph K_n, which is \binom{n}{2}, can be evenly divided between G and \overline{G}.[21] Consequently, a self-complementary graph must possess exactly m = \frac{\binom{n}{2}}{2} = \frac{n(n-1)}{4} edges, which is an integer under the above congruence condition.[4] A basic characterization of self-complementarity is the existence of a graph isomorphism \phi: V \to V such that for any distinct vertices u, v \in V, the edge \{u, v\} is present in E(G) if and only if \{\phi(u), \phi(v)\} is absent from E(G).[21] This permutation \phi effectively maps edges to non-edges and vice versa, preserving the graph's adjacency structure in the complement. Self-complementary graphs were first systematically studied in the early 1960s, independently by Horst Sachs and Gerhard Ringel.[21] Paley graphs, originally introduced by Raymond Paley in the context of quadratic residue tournaments, were recognized as prominent examples of self-complementary graphs due to their symmetric construction over finite fields.[22] No self-complementary graphs exist on 2 or 3 vertices, as these orders violate the necessary congruence condition on n.[4] On 1 vertex, there is exactly one trivial self-complementary graph, the empty graph K_1.[21]Constructions and Enumerations
One standard method to construct self-complementary graphs relies on a fixed-point-free involution on the vertex set, which pairs vertices such that the involution serves as an isomorphism from the graph to its complement. For a graph with $4k vertices, partition the vertices into $2k pairs via this involution \sigma, where \sigma^2 is the identity and no vertex is fixed. Edges are then defined by selecting, for each pair \{u, \sigma(u)\}, whether to include the edge u\sigma(u) (in which case the complement will exclude it, and vice versa), and for cross-pairs \{u, v\} where v \neq \sigma(u), including uv implies excluding \sigma(u)\sigma(v), ensuring the mapping preserves the structure. This approach, introduced by Sachs, guarantees self-complementarity as \sigma maps edges to non-edges and vice versa. For graphs of order q \equiv 1 \pmod{4} where q is a prime power, the Paley graph provides an explicit construction: take vertices as elements of the finite field \mathbb{F}_q, and connect two distinct vertices x and y if x - y is a nonzero quadratic residue in \mathbb{F}_q. This graph is self-complementary because multiplication by a non-residue maps residues to non-residues, inducing an isomorphism to the complement. Paley graphs are vertex-transitive and strongly regular, with the smallest example being the cycle C_5 on 5 vertices. Recursive constructions build larger self-complementary graphs from smaller ones, such as by vertex addition or cone-like operations. One method starts with a self-complementary graph H on $4k vertices and adds a new vertex connected to exactly $2k vertices of H in a way that preserves the isomorphism to the complement, often by selecting vertices based on the labeling from the involution. Another approach forms the cone over a self-complementary graph by adding an apex vertex adjacent to all others, but adjusts connections to maintain self-complementarity, typically requiring H to satisfy specific degree conditions. These techniques yield infinite families, including those with prescribed diameters.[21] The number of self-complementary graphs on n vertices is zero for n \equiv 2,3 \pmod{4}, as the edge count must be n(n-1)/4, which is non-integer otherwise. For small n, there is 1 on 4 vertices (the path P_4), 2 on 5 vertices (the cycle C_5 and the bull graph, which consists of a triangle with two pendant edges), and 10 on 8 vertices. The sequence grows rapidly: 36 on 9 vertices and 720 on 12 vertices, as catalogued by exhaustive enumeration. The full counts form OEIS sequence A000171.[23] The bull graph on 5 vertices exemplifies a non-cycle self-complementary graph, featuring a triangle adjacent to a path of length 2. The 10 self-complementary graphs on 8 vertices are all connected; these were fully enumerated and classified up to isomorphism.[23]Advanced Properties
Structural Properties
The clique number ω(G) of a graph G, which is the size of a largest clique in G, equals the independence number α(\bar{G}) of its complement \bar{G}. This relationship underscores the duality between maximal complete subgraphs in G and maximal independent sets in \bar{G}, a fundamental symmetry in graph complementation.[24] Regarding connectivity, if G is disconnected with at least two vertices, then \bar{G} is connected and has diameter at most 2. Vertices in different components of G are adjacent in \bar{G}, ensuring paths of length 1 between them; for vertices in the same component that are not adjacent in \bar{G} (i.e., adjacent in G), they share a common neighbor in \bar{G} from another component. Certain hereditary graph classes are closed under complementation, preserving their structural properties when taking complements. Cographs, defined recursively as the smallest class containing the single-vertex graph and closed under disjoint union and complementation, remain cographs under complementation by construction. Split graphs, whose vertices partition into a clique and an independent set, are also closed under complementation: the complement swaps the roles of the clique and independent set, yielding another split graph with the same partition sizes. Similarly, threshold graphs—a subclass of split graphs characterized by degree sequences realizable via a threshold function—are closed under complementation, as the complement's degree sequence satisfies the threshold condition equivalently.[25][26][27] For self-complementary graphs (isomorphic to their complements), those that are split or threshold graphs exhibit balanced partitions. In a self-complementary split graph on n vertices, the clique and independent set sizes differ by at most 1, partitioning the vertices evenly to ensure the isomorphism maps the clique to the independent set and vice versa. The same holds for self-complementary threshold graphs, inheriting this property from their split structure. The class of perfect graphs is closed under complementation, as established by Lovász's perfect graph theorem: a graph G is perfect if and only if its complement \bar{G} is perfect. This result, proved in 1972, implies that for perfect G, both G and \bar{G} satisfy the property that the chromatic number equals the clique number for every induced subgraph.[28]Spectral and Chromatic Properties
The chromatic number of a graph G with n vertices and its complement \overline{G} satisfies the Nordhaus-Gaddum inequalities: \chi(G) + \chi(\overline{G}) \leq n + 1 and \chi(G) \cdot \chi(\overline{G}) \leq \left\lfloor \frac{(n+1)^2}{4} \right\rfloor, with the upper bound on the sum being tight for complete and empty graphs. For connected graphs on n \geq 2 vertices, a lower bound holds: \chi(G) + \chi(\overline{G}) \geq n - 1.[29] Equality in the upper bound occurs when one graph is complete and the other is edgeless, while recent analyses confirm the bounds remain sharp across various graph classes, including those with specified connectivity. Post-2000 results have refined gap-related aspects, such as the maximum difference |\chi(G) - \chi(\overline{G})|, showing it can reach \Omega(\sqrt{n}) for certain constructions, though exact extremal values continue to be explored. Complements of bipartite graphs exhibit particularly strong chromatic properties: since bipartite graphs are perfect, their complements are also perfect by the strong perfect graph theorem, implying \chi(\overline{G}) = \omega(\overline{G}). This equality holds because perfect graphs are closed under complementation, avoiding induced odd holes and odd antiholes in both G and \overline{G}. The adjacency matrix of the complement satisfies A(\overline{G}) = J_n - I_n - A(G), where J_n is the all-ones matrix and I_n is the identity. For eigenvectors orthogonal to the all-ones vector, the eigenvalues of \overline{G} are -1 - \mu, where \mu are the corresponding eigenvalues of G.[30] In the context of Seidel switching, which generalizes complementation, the Seidel matrix S(G) = J_n - I_n - 2A(G) has eigenvalues that are negated for the complement: the spectrum of S(\overline{G}) is the negative of that of S(G). This relation underpins isospectral properties under switching operations.[31] The independence polynomial of G, defined as I(G; x) = \sum_{k=0}^{\alpha(G)} i_k x^k where i_k is the number of independent sets of size k, equals the clique polynomial of \overline{G}, C(\overline{G}; x) = \sum_{k=0}^{\omega(\overline{G})} c_k x^k with c_k the number of cliques of size k. This duality arises because independent sets in G correspond precisely to cliques in \overline{G}.Algorithmic Aspects
Computing Complements
To explicitly construct the complement graph from an adjacency list representation of the original graph G with n vertices, one iterates over all pairs of distinct vertices and adds an edge between those that are not adjacent in G. This process examines all \binom{n}{2} possible edges, resulting in O(n^2) time complexity.[32] For sparse graphs where the complement is dense, an explicit adjacency list for the complement would require storing nearly \binom{n}{2} edges, which is inefficient. Instead, an implicit representation stores only the adjacency information of G and determines non-adjacency in the complement via queries, avoiding the need to materialize the full edge set of size \binom{n}{2} - m, where m is the edge count in G. This approach is particularly useful when operations on the complement can be performed on-the-fly without full expansion. The adjacency matrix \overline{A} of the complement graph can be computed directly from the adjacency matrix A of G using the formula \overline{A} = J - I - A, where J is the n \times n all-ones matrix and I is the n \times n identity matrix. This matrix operation requires O(n^2) time and space, providing a straightforward way to obtain the complement's matrix representation.[1][33] Software libraries implement these methods efficiently for practical use. In NetworkX, thecomplement function generates the complement graph from an input graph, handling both undirected and directed cases while avoiding self-loops and parallel edges; it is optimized for graphs up to moderate sizes but may require O(n^2) time for dense outputs.[34] Similarly, igraph provides a complementer function that constructs the complement by including all missing edges from the original graph, suitable for dense complements in analytical workflows.[35]
For large graphs, especially sparse ones where the complement's density poses storage challenges, bitsets can represent the adjacency matrix compactly using approximately n^2 / 8 bytes, enabling efficient bit operations for queries and updates. Compressed formats, such as those in systems like Zuckerli, further reduce space for real-world large-scale graphs by exploiting structural redundancies in graph edge patterns.[36]