Perfection Requires Checking Every Induced Subgraph
A graph can have the same clique number and chromatic number without being perfect: perfection asks for that equality not just in the graph itself, but in every induced subgraph. Complete graphs and bipartite graphs provide two useful families where the equality can be checked systematically. The five-cycle gives a contrasting example: its clique number and chromatic number differ.
Throughout, graphs are finite and simple. For a set \(S\subseteq V(G)\), the induced subgraph \(G[S]\) has vertex set \(S\) and contains exactly those edges of \(G\) whose two endpoints both lie in \(S\). A clique is a set of pairwise adjacent vertices, and the clique number \(\omega(G)\) is the largest size of a clique. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors; the chromatic number \(\chi(G)\) is the least number of colors in a proper coloring.
For any graph, \(\omega(G)\leq\chi(G)\): the vertices of a clique are pairwise adjacent, so a proper coloring must give each of them a different color. Perfection is the special case in which this lower bound is attained in every induced subgraph. It is therefore important to keep the quantifier “every” in the definition: calculating \(\chi(G)\) and \(\omega(G)\) for the original graph alone does not in general settle whether \(G\) is perfect.
Complete Graphs Are Perfect
Proof. Let \(S\) be any subset of the vertices of \(K_n\), and let \(k=|S|\). Every pair of distinct vertices in \(S\) is adjacent, so \(K_n[S]\) is the complete graph on \(k\) vertices. If \(k=0\), our convention gives \(\chi(K_n[S])=\omega(K_n[S])=0\). If \(k\geq1\), all \(k\) vertices form a clique, so \(\omega(K_n[S])=k\). They also require \(k\) different colors, and assigning one different color to each vertex uses \(k\) colors, so \(\chi(K_n[S])=k\). Thus the two numbers agree for every \(S\), which proves that \(K_n\) is perfect. \(\square\)
Worked Example: The Complete Graph \(K_4\)
Let \(G=K_4\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). The edge list contains all six pairs of distinct vertices, as required for \(K_4\).
All four vertices are pairwise adjacent, so they form a clique and \(\omega(G)=4\). A proper coloring must assign different colors to all four vertices, while assigning four distinct colors does give a proper coloring. Hence \(\chi(G)=4\).
To check perfection, take any induced subgraph \(G[S]\). If \(S\) has \(k\) vertices, every pair in \(S\) remains an edge, so \(G[S]=K_k\). For \(k=0\), both numbers are \(0\); for \(k=1\), both are \(1\); for \(k=2\), both are \(2\); for \(k=3\), both are \(3\); and for \(k=4\), both are \(4\). These are all possible sizes of \(S\). Thus every induced subgraph has equal clique and chromatic numbers.
Check: The edge list has \(\binom{4}{2}=4\cdot3/2=6\) edges, matching the six listed pairs. The induced-subgraph calculation covers all possible vertex-set sizes, including the empty set.
Bipartite Graphs Are Perfect
A graph is bipartite if its vertex set can be partitioned into two sets \(X\) and \(Y\) such that each edge has one endpoint in \(X\) and one in \(Y\). Either part may be empty. A bipartite graph has no triangle: traversing a triangle would require alternating between \(X\) and \(Y\) at each edge, but after three steps the traversal cannot return to its starting part. Consequently, a bipartite graph has no clique of size greater than two.
Proof. Let \(G\) be bipartite with parts \(X,Y\), and let \(S\subseteq V(G)\). By the definition of an induced subgraph, the edges of \(G[S]\) are precisely the edges of \(G\) with both endpoints in \(S\). Each such edge still has one endpoint in \(X\cap S\) and one in \(Y\cap S\). Therefore \(G[S]\) is bipartite, with parts \(X\cap S\) and \(Y\cap S\).
If \(S=\varnothing\), then \(\chi(G[S])=\omega(G[S])=0\). Suppose next that \(S\neq\varnothing\). If \(G[S]\) has no edges, one color suffices, and at least one color is necessary because there is a vertex. Its largest clique is a single vertex. Hence \(\chi(G[S])=\omega(G[S])=1\).
It remains to consider the case where \(G[S]\) has at least one edge. Coloring \(X\cap S\) with one color and \(Y\cap S\) with another is proper, so \(\chi(G[S])\leq2\). The endpoints of an edge are adjacent, so they require different colors, giving \(\chi(G[S])\geq2\). Thus \(\chi(G[S])=2\). Those endpoints also form a clique of size two. Since \(G[S]\) has no triangle, it has no larger clique, so \(\omega(G[S])=2\). In every case the two numbers agree; this holds for every \(S\), proving that \(G\) is perfect. \(\square\)
Worked Example: A Bipartite Graph with an Isolated Vertex
Let \(G\) have \(V(G)=\{a,b,c,1,2\}\) and \(E(G)=\{a1,a2,b2\}\). Take \(X=\{a,b,c\}\) and \(Y=\{1,2\}\). Each listed edge joins the two parts, and \(c\) is isolated.
The graph has an edge, so its endpoints require at least two colors. Coloring \(a,b,c\) with red and \(1,2\) with blue is proper: the edges \(a1\), \(a2\) and \(b2\) all join different colors. Therefore \(\chi(G)=2\). The edge \(a1\) is a clique of size two. There is no triangle because every edge crosses between \(X\) and \(Y\); thus \(\omega(G)=2\).
Now take \(S=\{a,b,2,c\}\). Its induced edges are \(a2\) and \(b2\): the edge \(a1\) is absent because \(1\notin S\), and there are no other edges in the original graph. The induced subgraph has a two-coloring with \(\{a,b,c\}\) in one part and \(\{2\}\) in the other; its edge requires at least two colors. Its largest clique is an edge, so both numbers are \(2\). If instead \(S=\{a,c,1\}\), the only induced edge is \(a1\); \(c\) is isolated, and again \(\chi(G[S])=\omega(G[S])=2\).
Check: The three original edges are exactly \(a1,a2,b2\). In each selected induced subgraph, keeping only edges whose endpoints both belong to \(S\) gives the edge lists used above.
The Five-Cycle Is Imperfect
A cycle is not generally a clique: a clique requires every pair of its vertices to be adjacent, whereas a cycle only requires consecutive vertices to be adjacent. This distinction matters for the five-cycle. Its five vertices contain edges, but they do not form a five-vertex clique.
Worked Example: Comparing the Clique and Chromatic Numbers of \(C_5\)
Let \(G=C_5\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,51\}\). The edge list gives the cycle in the order \(1,2,3,4,5,1\).
The graph contains an edge, so \(\omega(G)\geq2\). No three vertices form a clique: each vertex has exactly two neighbors, and those two neighbors are not adjacent to each other in this edge list. A clique of size at least three would contain a triangle, so \(\omega(G)=2\).
Three colors suffice. Assign color A to vertices \(1,3\), color B to vertices \(2,4\), and color C to vertex \(5\). Checking the five edges: \(12\) has colors A and B; \(23\) has B and A; \(34\) has A and B; \(45\) has B and C; \(51\) has C and A. Thus the coloring is proper and \(\chi(G)\leq3\).
Two colors cannot suffice. If vertex \(1\) has color A, then edge \(12\) forces \(2\) to have color B; edge \(23\) forces \(3\) to have color A; edge \(34\) forces \(4\) to have color B; and edge \(45\) forces \(5\) to have color A. But edge \(51\) then has color A at both endpoints, contradicting properness. Hence \(\chi(G)\geq3\), so \(\chi(G)=3\).
Check: The computed values are \(\omega(G)=2\) and \(\chi(G)=3\), so they differ. Since \(G\) is itself an induced subgraph of \(G\), this one mismatch is enough to show that \(C_5\) is imperfect.
Reading the Examples Correctly
The complete-graph and bipartite-graph proofs use different structures. In a complete graph, every induced subgraph is complete, so its vertices all require distinct colors and all form a clique. In a bipartite graph, every induced subgraph remains bipartite; when it has an edge, two colors suffice and an edge forces two colors to be necessary. The empty and edgeless cases must be handled separately to make the bipartite argument complete.
The five-cycle shows why equality for the whole graph is the key test in an example of imperfection: it fails already at \(G\) itself. For a graph that does have \(\chi(G)=\omega(G)\), that calculation alone would not establish perfection; one must also check all its induced subgraphs or use a proof that covers them all.
Common mistake: treating a cycle as a clique. One might claim that \(\{1,3,5\}\) is a three-vertex clique in the five-cycle because those vertices are all part of the cycle. But the edge list contains neither \(13\), \(15\), nor \(35\), so these vertices are not pairwise adjacent. The clique number is \(2\), not \(3\). Conversely, checking only that some vertices are adjacent does not establish a larger clique: every pair in the proposed set must be adjacent.
These examples give a useful first test when studying a graph: compute \(\omega\) and \(\chi\) carefully, then remember what the comparison can establish. A mismatch proves that the graph is imperfect. Equality for the original graph is only one necessary check; perfection requires equality throughout the induced-subgraph family.
Check Your Understanding
For each question, state the relevant induced subgraphs or verify the listed edges rather than relying on a drawing.
- For \(K_3\), compute \(\chi\) and \(\omega\) for induced subgraphs of each possible order, including order zero.
- Explain why an induced subgraph of a bipartite graph with no edges has equal clique and chromatic numbers, both when it is empty and when it is nonempty.
- For the graph with \(V=\{a,b,c\}\) and \(E=\{ab\}\), find \(\chi\) and \(\omega\). Is the graph perfect?
- In the five-cycle with edge set \(\{12,23,34,45,51\}\), why does the set \(\{1,3,5\}\) fail to be a clique?
- Suppose a graph has \(\chi(G)=\omega(G)\). What additional condition must be checked to conclude that it is perfect?