Why Perfectness Uses Every Induced Subgraph
A coloring assigns colors to vertices so that adjacent vertices receive different colors. A clique is a set of pairwise adjacent vertices, and every vertex in a clique must receive a different color. Thus the size of a largest clique is a lower bound for the number of colors needed. A perfect graph is one for which this lower bound gives the exact answer not just for the graph itself, but for each of its induced subgraphs.
That last condition is essential. Checking only the whole graph compares two numbers once; it does not test what happens after selecting a subset of vertices and retaining all edges between them. The induced-subgraph condition makes perfectness hereditary: once a graph is perfect, the same equality holds throughout every induced subgraph. We will prove this directly from the definitions.
The condition concerns every vertex subset, not only subsets obtained by deleting one vertex. It also specifies which edges remain: when vertices are removed, all edges between the vertices left behind are retained. This is different from taking an arbitrary subgraph, where one could remove edges while keeping both of their endpoints.
The Basic Inequality
Proof. If \(G\) has no vertices, both quantities are \(0\), so the inequality holds. Otherwise, choose a clique \(C\) of largest size, so \(|C|=\omega(G)\). In any proper coloring, each pair of distinct vertices in \(C\) is adjacent and therefore has different colors. Consequently, the coloring uses at least \(|C|\) colors. This is true of every proper coloring, so the least possible number of colors satisfies \(\chi(G)\ge |C|=\omega(G)\). \(\square\)
This inequality explains why the equality in the definition is informative: the clique number is always a lower bound, and perfectness says that this bound is attained on every induced subgraph. For a graph to be perfect, equality for \(G\) itself is necessary, but it is not sufficient.
Why the Hereditary Property Holds
Proof. Let \(G\) be perfect, and let \(F=G[S]\) be any induced subgraph, where \(S\subseteq V(G)\). To prove that \(F\) is perfect, take an arbitrary induced subgraph of \(F\), say \(F[T]\), where \(T\subseteq S\). The vertex set of \(F[T]\) is \(T\). Its edges are exactly the edges of \(F\) with both endpoints in \(T\); since \(F=G[S]\), these are exactly the edges of \(G\) with both endpoints in \(T\). Hence \(F[T]=G[T]\). As \(G\) is perfect, its induced subgraph \(G[T]\) satisfies \(\chi(G[T])=\omega(G[T])\). Therefore \(\chi(F[T])=\omega(F[T])\). This holds for every \(T\subseteq S\), including \(T=\varnothing\), so \(F\) is perfect. \(\square\)
The proof uses only the definition of an induced subgraph and the universal quantifier in the definition of perfectness. In particular, it does not require a new coloring argument: each induced subgraph of \(F\) is already an induced subgraph of \(G\). The equality needed for \(F\) follows from the equality that perfectness of \(G\) supplies for that vertex subset.
For every vertex subset \(T\) of \(G\), the induced graph \(G[T]\) satisfies the required equality.
Write it as \(F=G[S]\) for some \(S\subseteq V(G)\).
For \(T\subseteq S\), retaining exactly the edges within \(T\) gives \(F[T]=G[T]\).
Since \(\chi(G[T])=\omega(G[T])\), the same equality holds for \(F[T]\). This works for every \(T\), so \(F\) is perfect.
Worked Examples: Reading the Quantifiers
Worked Example: A Complete Graph
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). We verify perfectness using the definition rather than checking only the whole graph.
Take any \(S\subseteq V(G)\), and let \(k=|S|\). Every pair of distinct vertices in \(S\) is an edge, so \(G[S]=K_k\) when \(k>0\). All \(k\) vertices form a clique, giving \(\omega(G[S])=k\). They also require \(k\) different colors, and assigning one distinct color to each vertex uses exactly \(k\), so \(\chi(G[S])=k\). If \(k=0\), the induced subgraph is empty and both numbers are \(0\). Thus every subset gives \(\chi(G[S])=\omega(G[S])\), and \(K_4\) is perfect.
Check: for \(S=\{1,3\}\), the induced graph has edge \(13\), so both numbers are \(2\). For \(S=\{1,3,4\}\), all three pairs are edges, so both numbers are \(3\). For \(S=\varnothing\), both are \(0\), as required by the convention.
Worked Example: An Edgeless Graph
Let \(G\) have \(V(G)=\{a,b,c\}\) and \(E(G)=\varnothing\). For any nonempty \(S\subseteq V(G)\), the induced graph \(G[S]\) has no edges. One color can be assigned to every vertex, and a single vertex is a clique, so \(\chi(G[S])=\omega(G[S])=1\). For \(S=\varnothing\), both numbers are \(0\). Therefore \(G\) is perfect.
Check: choosing \(S=\{a,c\}\) leaves two vertices and no edge. The whole set \(\{a,c\}\) is not a clique of size \(2\), because its vertices are not adjacent; the largest clique has size \(1\). Both vertices can receive the same color, so the chromatic number is also \(1\). This confirms why a nonempty edgeless graph has clique number \(1\), not \(0\).
Worked Example: Whole-Graph Equality Is Not Enough
Let \(G\) have vertex set \(\{1,2,3,4,5,a,b,c\}\). Its edges are \(12,23,34,45,51\) and \(ab,ac,bc\), with no edges between \(\{1,2,3,4,5\}\) and \(\{a,b,c\}\). The first five vertices form a 5-cycle, and the last three form a triangle.
First compute the chromatic number of the 5-cycle. Three colors suffice: assign color \(A\) to \(1\) and \(3\), color \(B\) to \(2\) and \(4\), and color \(C\) to \(5\). The five edges have endpoints of different colors: \(12\) has colors \(A,B\); \(23\) has \(B,A\); \(34\) has \(A,B\); \(45\) has \(B,C\); and \(51\) has \(C,A\). Two colors cannot suffice: starting with a color at \(1\), the edges \(12,23,34,45\) force alternating colors along the path \(1,2,3,4,5\), so \(5\) receives the same color as \(1\), contradicting the edge \(51\). Hence the cycle has chromatic number \(3\). Its largest clique has size \(2\): it has edges, but no triangle, so its clique number is \(2\).
The triangle on \(\{a,b,c\}\) has chromatic number \(3\) and clique number \(3\), since its three vertices are pairwise adjacent. A coloring of \(G\) needs at least three colors because of this triangle. Three colors suffice for \(G\): use the displayed three-coloring on the cycle and use three colors on the triangle. There are no edges between the two parts, so these assignments together form a proper coloring. Thus \(\chi(G)=3\).
A clique cannot contain vertices from both parts, since there are no edges between them. The largest clique is therefore the triangle, and \(\omega(G)=3\). So the whole graph satisfies \(\chi(G)=\omega(G)=3\). However, for \(S=\{1,2,3,4,5\}\), the induced subgraph \(G[S]\) is the 5-cycle, for which \(\chi(G[S])=3\) and \(\omega(G[S])=2\). The equality fails on this induced subgraph, so \(G\) is not perfect.
Check: the whole-graph equality is verified by the triangle lower bound and the explicit three-coloring. The induced-subgraph failure is verified independently by the odd cycle's forced alternating colors and its absence of a triangle. Thus a single equality for \(G\) does not satisfy the definition.
Common Mistakes and What the Definition Requires
Mistake: conclude perfectness from one equality. For the graph in the third example, the calculation \(\chi(G)=3=\omega(G)\) is correct. The incorrect step is concluding that \(G\) is perfect from that calculation. Perfectness requires the equality for every \(S\subseteq V(G)\); taking \(S=\{1,2,3,4,5\}\) gives \(\chi(G[S])=3\) and \(\omega(G[S])=2\), disproving perfectness.
Mistake: treat an arbitrary subgraph as an induced subgraph. An induced subgraph on \(S\) must retain every original edge whose endpoints lie in \(S\). If a calculation deletes one of those edges, it has instead formed a subgraph that may not be induced. The hereditary theorem applies to induced subgraphs because \(F[T]\) and \(G[T]\) have exactly the same vertices and edges; that identity is the key step in its proof.
There are two complementary ways to use the definition. To establish perfectness directly, one must check the equality for every induced subgraph, as in the complete and edgeless examples. To disprove perfectness, it is enough to find one vertex subset \(S\) for which the equality fails, as in the 5-cycle subset above. The basic inequality \(\omega(H)\le\chi(H)\) ensures that any such failure has \(\chi(H)>\omega(H)\).
Check Your Understanding
Use the definitions and proofs above to answer each question.
- Why does a proper coloring of a clique of size \(r\) require at least \(r\) colors?
- For a graph with no vertices, what values are assigned to its chromatic number and clique number, and why is it included in the definition of perfectness?
- In the hereditary-property proof, explain why \(F[T]=G[T]\) when \(F=G[S]\) and \(T\subseteq S\).
- Give the induced vertex subset in the third worked example that shows the graph is not perfect, and state both numbers for that induced subgraph.
- Why does checking \(\chi(G)=\omega(G)\) alone not establish that \(G\) is perfect?