Complementing a Graph
For a fixed vertex set, a simple graph chooses which pairs of distinct vertices are edges. Its complement makes the opposite choice: a pair is an edge in the complement exactly when it was not an edge in the original graph. This exchange turns two central kinds of vertex sets into one another. A set with no internal edges in a graph becomes a set with every possible internal edge in its complement.
A clique is a set of vertices in which every pair of distinct vertices is adjacent. An independent set is a set of vertices in which no pair of distinct vertices is adjacent. We use \(\omega(G)\) for the maximum size of a clique in \(G\), and \(\alpha(G)\) for the maximum size of an independent set in \(G\). The empty set is allowed as a clique and as an independent set. In particular, if \(V=\varnothing\), both parameters are \(0\). For a nonempty graph, each parameter is at least \(1\), since every singleton is both a clique and an independent set.
The complement keeps the vertices fixed; it does not create a new vertex for every nonedge or change the graph into a directed graph. To construct it, consider each unordered pair of distinct vertices once. If the pair is an edge in \(G\), leave it out of \(\overline{G}\); if it is not an edge in \(G\), include it.
The Basic Parameter Duality
Proof. Let \(S\subseteq V(G)\). The set \(S\) is a clique in \(\overline{G}\) exactly when every pair of distinct vertices in \(S\) is an edge of \(\overline{G}\). By the definition of the complement, this holds exactly when no pair of distinct vertices in \(S\) is an edge of \(G\). That is precisely the condition that \(S\) is an independent set in \(G\). Thus the cliques of \(\overline{G}\) and the independent sets of \(G\) are the same vertex subsets. Their maximum sizes are therefore equal: \(\omega(\overline{G})=\alpha(G)\). Apply this equality with \(\overline{G}\) in place of \(G\); since complementing twice restores every pair to its original status, \(\overline{\overline{G}}=G\), and hence \(\omega(G)=\alpha(\overline{G})\). The argument includes \(S=\varnothing\), so it also holds when \(V\) is empty. \(\square\)
This proof gives more than equality of two numbers: it gives a direct correspondence between the sets being optimized. Any independent set found in \(G\) is already a clique in \(\overline{G}\), with the same vertices, and any clique found in \(\overline{G}\) is independent in \(G\). This is why a problem about one parameter can sometimes be translated into a problem about the other graph.
Proof. There are \(\binom{n}{2}\) unordered pairs of distinct vertices in \(V(G)\). Each such pair is either an edge of \(G\) or an edge of \(\overline{G}\), and not both. Since \(m\) pairs are edges of \(G\), the number in the complement is \(\binom{n}{2}-m\). For each pair, complementing changes its status from edge to nonedge or from nonedge to edge. Complementing a second time restores its original status. The vertex set never changes, so \(\overline{\overline{G}}=G\). \(\square\)
The edge-count formula is a useful construction check. It counts all pairs once and partitions them into the edges of \(G\) and the edges of \(\overline{G}\). It also shows why the edge count alone does not specify the complement: the missing pairs, not just their number, determine where its edges go.
Worked Examples
Worked Example: A Path on Five Vertices
Let \(G=P_5\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45\}\). Its complement has the same five vertices. There are \(\binom{5}{2}=5\cdot4/2=10\) possible pairs, and the four pairs in \(E\) are excluded. Checking the remaining pairs gives \(E(\overline{G})=\{13,14,15,24,25,35\}\). The displayed complement has six edges, agreeing with \(10-4=6\).
In \(G\), the set \(\{1,3,5\}\) is independent: its three pairs are \(13,15,35\), and none is in \(E\). To bound the size of any independent set, partition the vertices into \(\{1,2\}\), \(\{3,4\}\), and \(\{5\}\). Each of the first two pairs is an edge of \(G\), so an independent set can take at most one vertex from each; the final singleton contributes at most one more. Therefore \(\alpha(G)\leq 1+1+1=3\), and the exhibited set shows \(\alpha(G)=3\).
The three pairs within \(\{1,3,5\}\) are all listed in \(E(\overline{G})\), so that set is a clique in the complement. The theorem gives \(\omega(\overline{G})=\alpha(G)=3\). As a direct upper-bound check, a clique in \(\overline{G}\) is independent in \(G\), and the partition argument has already ruled out an independent set of size \(4\).
Check: the complement list contains \(13,15,35\), so the proposed three-vertex clique really is complete. The edge count also checks: \(10\) total pairs split into \(4\) edges of \(G\) and \(6\) edges of \(\overline{G}\).
Worked Example: A Five-Cycle
Let \(G=C_5\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). There are \(\binom{5}{2}=5\cdot4/2=10\) possible pairs, so the complement has \(10-5=5\) edges. Removing the five cycle edges from the full list of pairs gives \(E(\overline{G})=\{13,14,24,25,35\}\).
The set \(\{1,3\}\) is independent in \(G\), since \(13\notin E\). No independent set can have three vertices: if three vertices are selected around the cycle, each selected vertex must be followed by an unselected vertex, or it would be adjacent to another selected vertex. The successors of distinct selected vertices are distinct, so three selected vertices would require at least three unselected vertices. Only two vertices remain when three are selected from this five-vertex graph. This contradiction proves \(\alpha(G)\leq2\), and thus \(\alpha(G)=2\).
In the complement, \(13\) is an edge, so \(\{1,3\}\) is a clique. The theorem gives \(\omega(\overline{G})=2\). In this case the complement is itself a five-cycle: its edges can be traced as \(13,35,52,24,41\), all of which appear in the complement edge list. Its three-vertex cliques are impossible by the same independent-set argument applied through the theorem.
Check: the complement has five listed edges, matching \(10-5=5\). The pair \(13\) verifies the lower bound of two for its clique number, while the argument establishing \(\alpha(G)=2\) and the proved correspondence rule out any larger clique.
Worked Example: A Six-Cycle
Let \(G=C_6\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61\}\). The number of possible pairs is \(\binom{6}{2}=6\cdot5/2=15\). Excluding the six cycle edges leaves \(E(\overline{G})=\{13,14,15,24,25,26,35,36,46\}\), which has \(15-6=9\) edges.
The set \(\{1,3,5\}\) is independent in \(G\): none of \(13,15,35\) is a cycle edge. The edges \(12,34,56\) partition the vertices into three adjacent pairs, so an independent set contains at most one endpoint of each pair and has size at most \(3\). It follows that \(\alpha(G)=3\).
Because \(13,15,35\) are all edges of \(\overline{G}\), the same set is a three-vertex clique there. By the theorem, the clique number cannot exceed \(\alpha(G)=3\), so \(\omega(\overline{G})=3\).
Check: the complement list contains nine edges, in agreement with the calculation \(15-6=9\). The three edges among \(1,3,5\) verify that the clique has size \(3\); the three adjacent pairs in \(G\) verify that no independent set, and hence no clique in the complement, can be larger.
Worked Example: A Complete Bipartite Graph
Let \(G=K_{2,3}\) have parts \(A=\{a,b\}\) and \(B=\{x,y,z\}\), with all six cross edges: \(V=\{a,b,x,y,z\}\) and \(E=\{ax,ay,az,bx,by,bz\}\). There are \(\binom{5}{2}=5\cdot4/2=10\) possible pairs. Six are edges of \(G\), so four are edges of its complement. In fact, \(E(\overline{G})=\{ab,xy,xz,yz\}\): these are the one pair within \(A\) and the three pairs within \(B\), with no edges between the two parts.
An independent set in \(G\) cannot contain both a vertex of \(A\) and a vertex of \(B\), because every such cross pair is an edge. Thus every independent set lies entirely within one part (or is empty). The larger part has three vertices, and \(B\) itself is independent, so \(\alpha(G)=3\).
In \(\overline{G}\), the vertices \(x,y,z\) form a triangle, meaning that all three pairs \(xy,xz,yz\) are edges. There are no complement edges from \(A\) to \(B\), so no clique can combine vertices from both parts. The largest clique is therefore \(\{x,y,z\}\), and \(\omega(\overline{G})=3=\alpha(G)\).
Check: the four complement edges give \(10-6=4\), as required by the pair count. The triangle confirms a clique of size \(3\); since its only other component has the two vertices \(a,b\), there is no larger clique.
Using the Duality Correctly
The identity is useful whenever the structure of one graph is easier to inspect than the other. For instance, a search for a large independent set in \(G\) can instead be viewed as a search for a large clique in \(\overline{G}\). Conversely, a statement that \(G\) has no independent set of size \(r\) translates exactly to the statement that \(\overline{G}\) has no clique of size \(r\). These are equivalent descriptions, not separate estimates.
A common mistake is to assume that a graph and its complement have the same clique number. For \(P_5\), the original graph has no triangle and does contain an edge, so its largest clique has size \(2\). But the complement contains all three edges \(13,15,35\), and therefore has a clique of size \(3\). The correct comparison is \(\omega(\overline{G})=\alpha(G)\), not \(\omega(\overline{G})=\omega(G)\). For this path, the independent set \(\{1,3,5\}\) explains the complement’s larger clique.
Another error is to take the complement of an edge list without first fixing the vertex set. A graph’s complement includes every original vertex, even isolated ones, and considers every pair of distinct vertices on that set. In particular, an omitted edge is not omitted from consideration: it becomes an edge of the complement. The pair-count formula provides a quick way to catch a list that is too short or too long.
Check Your Understanding
For each question, specify the vertex set when constructing a complement. Use the set correspondence in the theorem to justify conclusions about maximum sizes.
- Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23\}\). List \(E(\overline{G})\), then find an independent set of maximum size in \(G\) and a clique of the same size in \(\overline{G}\).
- Explain why an independent set of size \(r\) in \(G\) gives a clique of size \(r\) in \(\overline{G}\), including the case \(r=0\).
- A simple graph has six vertices and seven edges. How many edges does its complement have? Show the pair count used.
- If \(\omega(G)=4\), what is \(\alpha(\overline{G})\)? State which complement identity justifies the answer.
- Give a concrete reason that the claim \(\omega(\overline{G})=\omega(G)\) does not hold for every graph, using the five-vertex path example.