Why Cliques Give Color Lower Bounds
In a proper vertex coloring, adjacent vertices must receive different colors. A clique is a set in which every pair of distinct vertices is adjacent, so its vertices have an especially strong restriction: no two of them can share a color. Finding a large clique therefore gives a direct lower bound on the number of colors needed for the whole graph.
Throughout, graphs are finite and simple. A proper coloring of \(G=(V,E)\) assigns a color to every vertex so that the endpoints of every edge receive different colors. The chromatic number \(\chi(G)\) is the least number of colors in a proper coloring. We use \(\chi(G)=0\) for a graph with no vertices. A clique is a set of vertices in which every two distinct vertices are adjacent. A clique of size \(r\) is also a complete subgraph on \(r\) vertices. The clique number \(\omega(G)\) is the largest size of a clique; for the graph with no vertices, set \(\omega(G)=0\).
The phrase “lower bound” matters. A clique certifies that fewer colors cannot work, but it does not by itself produce a coloring with that many colors. To determine \(\chi(G)\) exactly, one also needs an upper bound, usually a proper coloring using a stated number of colors. The clique number and the chromatic number measure different features of a graph, even though one always bounds the other in this direction.
The Clique Lower-Bound Theorem
Proof. Let \(c\) be any proper coloring of \(G\), and take two distinct vertices \(u,v\in C\). Because \(C\) is a clique, \(uv\in E\). The coloring is proper, so \(c(u)\ne c(v)\). This applies to every pair of distinct vertices in \(C\); thus the colors assigned to its \(r\) vertices are all distinct. \(\square\)
Proof. If \(G\) has no vertices, both parameters are defined to be \(0\), and the inequality holds. Otherwise, finiteness ensures that a largest clique exists; let \(C\) be one, with \(|C|=\omega(G)\). By the proposition, every proper coloring of \(G\) uses at least \(|C|\) distinct colors on \(C\). In particular, every proper coloring of \(G\) uses at least \(\omega(G)\) colors. Taking the least number of colors over all proper colorings gives \(\chi(G)\ge\omega(G)\). A proper coloring exists, since assigning a separate color to each vertex works, so this least number is well-defined. \(\square\)
This reasoning does not depend on coloring the vertices outside the clique in any particular way. They may require more colors, or they may be colored using colors already assigned to clique vertices, provided no edge has equal-colored endpoints. The clique itself supplies a lower bound regardless of those other choices.
Using a Maximum Clique
A clique of any size gives a valid bound. To obtain the strongest bound of this form, find a maximum clique, meaning a clique with largest possible cardinality. This is distinct from a maximal clique, which is one that cannot be enlarged by adding another vertex. A maximal clique need not be maximum: another clique elsewhere in the graph can be larger.
Worked Example: A Triangle with Pendant Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,23,14,25\}\). Find \(\omega(G)\) and the resulting lower bound on \(\chi(G)\).
The vertices \(\{1,2,3\}\) form a clique: the three required edges are \(12\), \(13\), and \(23\), and all belong to \(E\). Its size is \(3\), so \(\omega(G)\ge3\).
To check that no larger clique exists, note that vertex \(4\) is adjacent only to \(1\), and vertex \(5\) is adjacent only to \(2\). A clique containing \(4\) can therefore contain at most one other vertex, and the same is true of a clique containing \(5\). Any clique of size at least \(3\) must consequently lie inside \(\{1,2,3\}\). Since that set has size \(3\), no clique can be larger than the one already found. Thus \(\omega(G)=3\).
The theorem gives \(\chi(G)\ge\omega(G)=3\). The specific certificate is the triangle: its three mutually adjacent vertices require three distinct colors. This conclusion is a lower bound; it does not claim that three colors suffice for all of \(G\).
Check: the clique contains exactly the vertices \(1,2,3\), with the three pairwise edges \(12,13,23\). The two remaining vertices cannot enlarge it: \(4\) is not adjacent to \(2\) or \(3\), and \(5\) is not adjacent to \(1\) or \(3\). The maximum clique size is therefore \(3\).
Worked Example: A Four-Vertex Clique with Two Additional Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,13,14,23,24,34,15,25,36,46,56\}\). Find the clique number and the chromatic-number lower bound.
The set \(\{1,2,3,4\}\) is a clique. Its six pairs are \(12,13,14,23,24,34\), and each is an edge in \(E\). This gives \(\omega(G)\ge4\).
Now check that no larger clique exists. The neighbors of \(5\) are \(1,2,6\), and the neighbors of \(6\) are \(3,4,5\). Their only common neighbor among the vertices other than \(5\) and \(6\) is none: \(1,2\) are not neighbors of \(6\), while \(3,4\) are not neighbors of \(5\). Thus, if a clique contains both \(5\) and \(6\), it cannot contain any further vertex, so it has size at most \(2\).
If a clique contains \(5\) but not \(6\), its other vertices must be among \(1,2\). Hence it has size at most \(3\). If it contains \(6\) but not \(5\), its other vertices must be among \(3,4\), so it too has size at most \(3\). A clique containing neither \(5\) nor \(6\) lies in \(\{1,2,3,4\}\), so it has size at most \(4\). Together these cases show that no clique has size greater than \(4\). Therefore \(\omega(G)=4\).
It follows that \(\chi(G)\ge\omega(G)=4\). In particular, any proposed proper coloring using at most three colors must fail: among vertices \(1,2,3,4\), all four colors must be different.
Check: the four vertices \(1,2,3,4\) have all six pairwise edges, giving a clique of size \(4\). The cases above bound every clique involving \(5\) or \(6\) by \(3\), except a clique containing both, which has size at most \(2\). The maximum clique size is exactly \(4\).
Worked Example: A Star Gives a Smaller Lower Bound
Let \(G=(V,E)\), where \(V=\{0,1,2,3,4\}\) and \(E=\{01,02,03,04\}\). Determine \(\omega(G)\) and the bound on \(\chi(G)\).
Every pair consisting of the center \(0\) and a leaf is an edge. For example, \(\{0,1\}\) is a clique, so \(\omega(G)\ge2\). No two leaves are adjacent: the edge set contains no edge \(ij\) with distinct \(i,j\in\{1,2,3,4\}\). A clique can contain at most one leaf, and therefore can contain at most two vertices in total, including the center. Hence \(\omega(G)=2\).
The clique theorem gives \(\chi(G)\ge\omega(G)=2\). The reason this lower bound is small is that the largest mutually adjacent set in the graph has only two vertices. This example also emphasizes the scope of the conclusion: a clique argument gives a necessary number of colors, not automatically the exact number needed.
Check: each of the four listed edges gives a two-vertex clique with \(0\). There is no edge between any two leaves, so no clique has three vertices. Thus the largest clique has size \(2\).
Subgraphs and Clique Certificates
A clique is often identified inside a larger graph without listing all of its vertices. The following fact explains why that is enough. A subgraph \(H\) of \(G\) has vertices and edges drawn from \(G\); in particular, every edge of \(H\) is also an edge of \(G\).
Proof. Every clique of \(H\) consists of vertices whose pairwise edges belong to \(H\). Since every edge of \(H\) is also an edge of \(G\), those same vertices form a clique in \(G\). Therefore the largest clique size in \(H\) cannot exceed the largest clique size in \(G\). If \(H\) has no vertices, its clique number is \(0\), and the inequality still holds. \(\square\)
For a color lower bound, the useful object is not necessarily the entire subgraph but its clique. If a graph contains a clique of size \(r\), then it needs at least \(r\) colors, whether or not that clique is maximum. A maximum clique improves the bound among all such certificates, but finding a maximum is not necessary to prove a particular lower bound.
This is useful when testing a coloring proposal. If the graph contains a clique of size \(r\), any proposed coloring with fewer than \(r\) colors can be rejected immediately, without checking every edge. Conversely, passing the clique test does not verify that a coloring is proper: edges outside the clique can still have endpoints of the same color. The lower-bound certificate and the edge-by-edge coloring check answer different questions.
Common Mistake: Maximal Is Not Maximum
Suppose \(G=(V,E)\) has \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,13,23,45,46,47,56,57,67\}\). The vertices \(1,2,3\) form a triangle, and none of the other vertices is adjacent to any of them. The vertices \(4,5,6,7\) form a clique, since all six pairs among them are edges.
A mistaken argument might say: “I found the maximal clique \(\{1,2,3\}\), so \(\omega(G)=3\), and therefore \(\chi(G)\ge3\).” The lower-bound conclusion \(\chi(G)\ge3\) is valid, but the claimed value of \(\omega(G)\) is not. The clique \(\{1,2,3\}\) is maximal because no vertex can be added to it; nevertheless, \(\{4,5,6,7\}\) is a larger clique. The correction is to compare the candidate against all possible cliques, or otherwise prove that no larger one exists. Here the four-vertex clique gives \(\omega(G)\ge4\), and there are only seven vertices, while the only other component is the triangle; hence no clique has more than four vertices. Thus \(\omega(G)=4\) and \(\chi(G)\ge4\).
More generally, finding one clique of size \(r\) proves \(\omega(G)\ge r\), not equality. Equality requires an additional argument ruling out every larger clique. This distinction is important because the theorem uses the maximum clique size, while a single discovered clique supplies only the bound corresponding to its own size.
Check Your Understanding
For each question, distinguish what a clique proves from what would require a separate coloring argument.
- Explain why a clique of size \(5\) forces at least five distinct colors in every proper coloring.
- A graph contains a clique of size \(4\), but no maximum-clique calculation is known. What lower bound on its chromatic number follows?
- Give an argument that a clique found in a subgraph is also a clique in the full graph.
- In the star example, why does the absence of edges between leaves rule out a clique of size \(3\)?
- Explain the difference between a maximal clique and a maximum clique, and why finding a maximal clique alone may not determine \(\omega(G)\).