The Weak Perfect Graph Theorem

Perfectness and Complementation

A graph and its complement have opposite adjacency rules: every pair of distinct vertices is an edge in exactly one of them. This changes cliques into independent sets, and changes proper colorings into partitions into cliques. The Weak Perfect Graph Theorem says that, despite these changes, perfectness is preserved: a graph is perfect if and only if its complement is perfect.

All graphs in this tutorial are finite and simple. A clique is a set of pairwise adjacent vertices, and an independent set is a set of pairwise nonadjacent vertices. The clique number \(\omega(G)\) is the largest size of a clique in \(G\), and the independence number \(\alpha(G)\) is the largest size of an independent set. The chromatic number \(\chi(G)\) is the least number of colors in a proper vertex coloring: adjacent vertices must receive different colors. For the graph with no vertices, set \(\omega(G)=\alpha(G)=\chi(G)=0\).

The requirement applies to every vertex subset, not just to the whole graph. An induced subgraph \(G[S]\) retains precisely the edges of \(G\) whose two endpoints belong to \(S\). The empty set is included in the definition; its induced subgraph has both parameters equal to zero.

What Complementation Does to the Parameters

Proof. A set of vertices is a clique in \(\overline{G}\) precisely when every pair in it is an edge of \(\overline{G}\), which means that no pair in it is an edge of \(G\). Thus it is an independent set in \(G\), and the largest possible sizes are equal: \(\omega(\overline{G})=\alpha(G)\). Reversing the roles of \(G\) and \(\overline{G}\) gives \(\alpha(\overline{G})=\omega(G)\). For the induced-subgraph identity, take any two distinct vertices in \(S\). They are adjacent in \(\overline{G[S]}\) exactly when they are not adjacent in \(G[S]\), which holds exactly when they are not adjacent in \(G\). This is also exactly the condition for their being adjacent in \(\overline{G}[S]\). Both graphs have vertex set \(S\), so they are equal. \(\square\)

There is a related interpretation of coloring. A clique partition of \(G\) is a partition of \(V(G)\) into sets that are cliques in \(G\). Let \(q(G)\) be the minimum number of parts in such a partition, and set \(q(G)=0\) for the empty graph. Each color class in a proper coloring of \(\overline{G}\) is an independent set in \(\overline{G}\), hence a clique in \(G\). Conversely, each clique partition of \(G\) gives a proper coloring of \(\overline{G}\). Therefore \(\chi(\overline{G})=q(G)\).

Consequently, the assertion that \(\overline{G}\) is perfect can be read entirely in terms of \(G\): for every \(S\subseteq V(G)\), the minimum number of cliques partitioning \(G[S]\) must equal \(\alpha(G[S])\). This reformulation explains why the theorem is not an immediate consequence of the identity between clique number and independence number. It also involves the number of colors needed, or equivalently the minimum size of a clique partition.

The Weak Perfect Graph Theorem

This is a classical, deep theorem. Its proof is not developed here; the theorem is stated as a standard result rather than presented as if the parameter identities above proved it. Those identities do give a useful way to understand what the theorem asserts. For each \(S\), the induced subgraph \(\overline{G}[S]\) has clique number \(\alpha(G[S])\), while its chromatic number is \(q(G[S])\). Thus perfectness of \(\overline{G}\) says that \(q(G[S])=\alpha(G[S])\) for every \(S\). The theorem says this condition holds whenever \(G\) is perfect, and conversely.

The “if and only if” includes both directions. The forward direction says that perfectness of \(G\) guarantees perfectness of \(\overline{G}\). For the reverse direction, apply the same forward direction to \(\overline{G}\): its complement is \(G\), because complementing twice restores every adjacency decision. This gives perfectness of \(G\) when \(\overline{G}\) is perfect.

Using the Theorem Carefully

The theorem is especially useful when a complement is simpler to analyze than the original graph. One may establish perfectness for the simpler graph and then transfer the conclusion to its complement. The theorem also transfers failure: if one graph is not perfect, its complement cannot be perfect, since the “if and only if” would otherwise imply that the first graph is perfect.

Common pitfall: checking only the whole graph. The equality \(\chi(G)=\omega(G)\) by itself does not establish that \(G\) is perfect. The definition requires equality for every induced subgraph. For example, the graph \(G\) in the triangle-and-isolated-vertex example has \(\chi(G)=\omega(G)=3\), but that equality alone would not have checked all its induced subgraphs. The example is perfect only after the induced-subgraph cases are accounted for.

Common pitfall: confusing the two parameter identities. The identity \(\omega(\overline{G})=\alpha(G)\) concerns clique size, not chromatic number. In general, coloring \(\overline{G}\) requires partitioning \(G\) into cliques; it does not follow just by substituting \(\alpha(G)\) for \(\chi(\overline{G})\). The theorem is the substantive result that guarantees the relevant equalities across all induced subgraphs when \(G\) is perfect.