Cliques and Missing Edges
A clique is a set of vertices in which every pair is joined by an edge. It describes a group whose members are all mutually adjacent. A graph complement reverses adjacency: among distinct vertices, it places an edge exactly where the original graph does not. This gives a useful translation between two ways of describing a vertex set: being fully joined in a graph, and having no adjacent pair in its complement.
All graphs in this tutorial are finite and simple. For a graph \(G=(V,E)\), an unordered pair of distinct vertices is written \(uv\). A set \(S\subseteq V\) is a clique if \(uv\in E\) for every two distinct vertices \(u,v\in S\). A set \(S\subseteq V\) is independent if \(uv\notin E\) for every two distinct vertices \(u,v\in S\). A one-vertex set, and also the empty set, satisfy both definitions.
The vertex set does not change when taking a complement; only the edge set changes. For \(n=|V|\), there are \(n(n-1)/2\) possible edges between distinct vertices. Each such pair is an edge of exactly one of \(G\) and \(\overline{G}\). Therefore
This count also handles \(n=0\) and \(n=1\): in either case there are no possible edges. The formula is a practical check when constructing a complement, but it does not replace checking which particular pairs are present.
Basic Properties of the Complement
Proof. The graphs \(G\) and \(\overline{\overline{G}}\) have the same vertex set \(V(G)\), since taking a complement preserves the vertex set. Consider any pair \(u,v\) of distinct vertices. If \(uv\in E(G)\), then \(uv\notin E(\overline{G})\), so \(uv\in E(\overline{\overline{G}})\). If \(uv\notin E(G)\), then \(uv\in E(\overline{G})\), so \(uv\notin E(\overline{\overline{G}})\). Thus exactly the same pairs are edges in \(G\) and \(\overline{\overline{G}}\). Neither graph has loops, so their edge sets agree completely. \(\square\)
The definition also gives the key correspondence. A set of vertices is a clique in \(G\) precisely when every pair in it is absent from \(\overline{G}\), which is precisely when that set is independent in \(\overline{G}\). The next theorem turns this correspondence into an equality of numerical parameters.
Proof. Let \(S\subseteq V(G)\). For each pair of distinct vertices \(u,v\in S\), the definition of the complement says that \(uv\in E(G)\) if and only if \(uv\notin E(\overline{G})\). Consequently, \(S\) is a clique in \(G\) if and only if \(S\) is an independent set in \(\overline{G}\). The two kinds of sets therefore have exactly the same possible sizes. Their largest sizes are equal, giving \(\omega(G)=\alpha(\overline{G})\). If \(V(G)=\varnothing\), the only subset is the empty set, and both largest sizes are \(0\) by definition, so the result includes that case. \(\square\)
The theorem is about a graph and its complement, not about two parameters of the same graph. It lets us rephrase a question about fully adjacent groups as a question about groups with no internal edges after complementing. It does not claim that taking a complement makes a search or computation automatically easier; it gives an exact translation between the structures being sought.
Worked Examples
Worked Example: The Complement of a Four-Vertex Path
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). Construct \(\overline{G}\), then find \(\omega(G)\) and \(\alpha(\overline{G})\).
There are \(4\cdot3/2=6\) possible edges: \(12,13,14,23,24,34\). Removing the three edges of \(G\) leaves \(E(\overline{G})=\{13,14,24\}\). The count checks: \(3+3=6\), as required.
In \(G\), the edges themselves are cliques of size \(2\), so \(\omega(G)\ge 2\). No three vertices form a clique: among the four triples, \(\{1,2,3\}\) lacks \(13\), \(\{1,2,4\}\) lacks \(14\), \(\{1,3,4\}\) lacks \(14\), and \(\{2,3,4\}\) lacks \(24\). Thus \(\omega(G)=2\).
In \(\overline{G}\), the pair \(\{1,2\}\) is independent because \(12\notin E(\overline{G})\), so \(\alpha(\overline{G})\ge2\). None of its four triples is independent: \(\{1,2,3\}\) contains edge \(13\); \(\{1,2,4\}\) contains \(14\) and \(24\); \(\{1,3,4\}\) contains \(13\) and \(14\); and \(\{2,3,4\}\) contains \(24\). Therefore \(\alpha(\overline{G})=2\).
Check: both parameters are \(2\), and the edge counts add to the six possible pairs. The result agrees with the theorem.
Worked Example: Complementing a Five-Cycle
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,15\}\). Find its complement and compare the two parameters.
There are \(5\cdot4/2=10\) possible edges. The pairs not in \(E\) are \(13,14,24,25,35\), so \(E(\overline{G})=\{13,14,24,25,35\}\). These are the edges of the cycle in the order \(1,3,5,2,4,1\); the list includes \(13,35,52,24,41\), where \(52=25\) and \(41=14\). Thus both \(G\) and \(\overline{G}\) are five-cycles, and the edge count is \(5+5=10\).
No three vertices form a clique in \(G\): every vertex of this cycle has exactly two neighbors, and those two neighbors are not adjacent to one another. Hence a triangle cannot occur, while any edge supplies a clique of size \(2\). So \(\omega(G)=2\).
For the independence number of \(\overline{G}\), an edge of the five-cycle cannot have both endpoints in an independent set. If three vertices were independent, then as we go around the cycle, at least one unchosen vertex would have to separate each consecutive pair of chosen vertices. Three chosen vertices and three separating unchosen vertices would require at least six vertices, but the cycle has only five. Thus no independent set has size \(3\) or more. The pair \(\{1,2\}\) is independent in \(\overline{G}\), since \(12\) is not one of its edges, so \(\alpha(\overline{G})=2\).
Check: the five-cycle in \(G\) has no triangle, and the explicitly listed complement is also a five-cycle. The computed values are \(\omega(G)=2=\alpha(\overline{G})\).
Worked Example: Complement of a Star
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,14\}\), a star with center \(1\). Find both parameters in the theorem.
The six possible pairs are \(12,13,14,23,24,34\). The missing pairs are \(23,24,34\), so \(E(\overline{G})=\{23,24,34\}\). The complement has vertex \(1\) isolated and the other three vertices mutually adjacent. Again, the edge count checks: \(3+3=6\).
In \(G\), each edge gives a clique of size \(2\). A clique cannot contain two leaves, because no two of \(2,3,4\) are adjacent in \(G\). Thus every clique has size at most \(2\), and \(\omega(G)=2\).
In \(\overline{G}\), the three vertices \(2,3,4\) are pairwise adjacent, so no independent set can contain more than one of them. Vertex \(1\) is isolated and can be included with any one of those three vertices. For example, \(\{1,2\}\) is independent. Therefore \(\alpha(\overline{G})=2\).
Check: a clique of size \(2\) in \(G\), such as \(\{1,2\}\), is an independent set of size \(2\) in \(\overline{G}\). The isolated vertex in the complement does not make a larger independent set, because its other three vertices are pairwise adjacent.
Common Pitfalls and Uses
Do not confuse the graph with its complement. In the path example, a mistaken complement might be listed as \(12,23,34\), simply repeating the original edges. That is not a complement: those pairs are present in \(G\), so none can be an edge of \(\overline{G}\). The correction is to list all six possible pairs first, then retain only the missing ones, giving \(13,14,24\).
Do not drop the bar from the identity. In the star example, \(\omega(G)=2\), whereas \(\alpha(G)=3\), since the three leaves are independent in \(G\). Thus \(\omega(G)=\alpha(G)\) is false in this example. The correct equality is \(\omega(G)=\alpha(\overline{G})\): the complement’s independent sets correspond to the original graph’s cliques.
The correspondence can be useful whenever a problem is naturally stated in terms of mutual adjacency but independent sets are the more convenient language, or vice versa. To apply it reliably, keep the vertex set fixed, identify the missing edges accurately, and check the parameter on the appropriate graph. The theorem concerns the largest sizes; its proof works because the correspondence applies to every vertex subset, not just to one particular example.
Check Your Understanding
Use the definitions to answer each question. When constructing a complement, account for every pair of distinct vertices.
- For \(V=\{a,b,c\}\) and \(E=\{ab\}\), list the complement’s edge set and compute \(\omega(G)\) and \(\alpha(\overline{G})\).
- Explain why the empty set is both a clique and an independent set, and state the two parameters for the graph with no vertices.
- Prove that if \(S\) is a clique in \(G\), then \(S\) is independent in \(\overline{G}\).
- A graph has five vertices and seven edges. How many edges does its complement have? Justify the count using the possible unordered pairs.
- Give a graph for which \(\omega(G)\ne\alpha(G)\), and check whether \(\omega(G)=\alpha(\overline{G})\) holds.