From Bounds to an Exact Answer
Finding a proper coloring with a small number of colors gives an upper bound on a graph’s chromatic number. Proving that fewer colors cannot work gives a lower bound. When the two bounds meet, they certify the exact answer. The practical challenge is to provide evidence for both sides: an explicit coloring for the upper bound, and a clique or another obstruction to fewer colors for the lower bound.
Throughout, graphs are finite and simple. A proper vertex coloring assigns a color to each vertex so that the endpoints of every edge have different colors. The chromatic number \(\chi(G)\) is the least number of colors in a proper coloring of \(G\). A clique is a set of pairwise adjacent vertices. The clique number \(\omega(G)\) is the largest size of a clique.
For a nonempty graph, a coloring using \(k\) colors proves \(\chi(G)\le k\). A clique of size \(k\) proves \(\chi(G)\ge k\), since every pair of its vertices is adjacent and so its vertices must receive distinct colors. A particularly efficient certificate uses a coloring and a clique of the same size. But a clique is not the only way to prove a lower bound: a subgraph that needs many colors also forces the whole graph to need at least that many.
Why the Bounds Are Valid
Proof. If \(G\) is empty, then both quantities are zero under the convention \(\chi(G)=\omega(G)=0\), so the inequality holds. Otherwise, take any clique \(Q\) in \(G\). Each pair of distinct vertices of \(Q\) is joined by an edge. In every proper coloring, those two endpoints must have different colors. Thus all vertices of \(Q\) receive distinct colors, so every proper coloring uses at least \(|Q|\) colors. This holds for every clique \(Q\), including one of maximum size; therefore \(\chi(G)\ge\omega(G)\). \(\square\)
Proof. If \(G\) is empty, then \(H\) is empty and both chromatic numbers are zero. Otherwise, take a proper coloring of \(G\) that uses \(\chi(G)\) colors. Restrict that assignment to the vertices of \(H\). Every edge of \(H\) is also an edge of \(G\), so its endpoints had different colors in the original coloring and still have different colors after restriction. The restriction is a proper coloring of \(H\), using at most \(\chi(G)\) colors. By the definition of \(\chi(H)\), it follows that \(\chi(H)\le\chi(G)\). \(\square\)
These results explain two common lower-bound certificates. A clique is a subgraph whose vertices require distinct colors. More generally, if a subgraph requires \(k\) colors for another reason, the whole graph also requires at least \(k\). To certify an exact value, present the upper bound and the lower-bound argument separately; neither one alone establishes equality.
A Reliable Certificate Procedure
For a small graph given by its edge list, work in two directions. First propose color classes and check each listed edge. Then seek a lower-bound witness: often a clique, and sometimes a subgraph or a direct argument that fewer colors would force a contradiction.
State the full vertex set and edge set. This makes it possible to check that no edge is overlooked.
List the color assigned to each vertex, or give the color classes. Check that each edge has endpoints in different classes.
Identify a clique or a subgraph that needs a stated number of colors, and explain why fewer cannot work.
If the coloring uses \(k\) colors and the lower-bound proof shows that at least \(k\) are necessary, conclude \(\chi(G)=k\).
A proposed coloring should be checked against the edges, not just described as “alternating” or “obvious.” Likewise, a lower bound must rule out every coloring with fewer colors, not merely show that one chosen coloring uses many colors.
Worked Example: A Clique Certifies Four Colors
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 \(\chi(G)\).
The vertices \(\{1,2,3,4\}\) form a clique: the edge list contains all six pairs \(12,13,14,23,24,34\). By the clique lower bound, \(\chi(G)\ge4\).
For an upper bound, use the color classes \(A=\{1,6\}\), \(B=\{2\}\), \(C=\{3,5\}\), and \(D=\{4\}\). This assignment uses four colors. Check every edge: \(12\) joins \(A\) to \(B\); \(13\) joins \(A\) to \(C\); \(14\) joins \(A\) to \(D\); \(23\) joins \(B\) to \(C\); \(24\) joins \(B\) to \(D\); \(34\) joins \(C\) to \(D\); \(15\) joins \(A\) to \(C\); \(25\) joins \(B\) to \(C\); \(36\) joins \(C\) to \(A\); \(46\) joins \(D\) to \(A\); and \(56\) joins \(C\) to \(A\). Every edge has differently colored endpoints.
Check: the coloring gives \(\chi(G)\le4\), while the displayed four-vertex clique gives \(\chi(G)\ge4\). Hence \(\chi(G)=4\).
When the Clique Bound Is Not Enough
The clique lower bound is useful, but it need not be the strongest available bound. In particular, a graph may need more colors than the size of its largest clique. A different obstruction can then finish the certificate. An odd cycle, for example, cannot be properly colored with just two colors: the colors would have to alternate around the cycle and fail at the closing edge. The next example uses this obstruction together with a coloring.
Worked Example: An Odd Cycle Forces Three Colors
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,51,16\}\). The first five vertices form a cycle, and vertex \(6\) is joined only to vertex \(1\). Find \(\chi(G)\).
Assign colors by \(1=A,\ 2=B,\ 3=A,\ 4=B,\ 5=C,\ 6=B\). The edge checks are \(12:A\text{--}B\), \(23:B\text{--}A\), \(34:A\text{--}B\), \(45:B\text{--}C\), \(51:C\text{--}A\), and \(16:A\text{--}B\). Each edge joins differently colored vertices, so \(\chi(G)\le3\).
For the lower bound, suppose the graph had a proper coloring with at most two colors. Along the cycle, vertices \(1\) and \(2\) must have different colors. Then \(3\) must have the same color as \(1\), \(4\) the same color as \(2\), and \(5\) the same color as \(1\). But \(51\) is an edge, and \(5\) and \(1\) would have the same color. This contradiction rules out a two-coloring, so \(\chi(G)\ge3\).
Check: the explicit coloring proves the upper bound \(3\), and the cycle argument proves the lower bound \(3\). Therefore \(\chi(G)=3\). The largest clique has size \(2\): the graph has no triangle, since the edge list contains no three vertices with all three connecting edges. The clique bound alone would only give a lower bound of \(2\); the odd-cycle argument supplies the stronger one.
The lower-bound argument is specific to the subgraph being used. It does not claim that every subgraph with several edges requires many colors; it gives a reason, in this case an odd cycle, that fewer colors are impossible. Once that reason is established for a subgraph, the subgraph lower-bound theorem transfers it to the whole graph.
Worked Example: Four Colors Without a Four-Vertex Clique
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,51,16,26,36,46,56\}\). Vertices \(1,2,3,4,5\) form a cycle, and vertex \(6\) is adjacent to all five cycle vertices. Find \(\chi(G)\).
For an upper bound, give the rim vertices the colors \(1=A,\ 2=B,\ 3=A,\ 4=B,\ 5=C\), and give vertex \(6\) color \(D\). The rim edges \(12,23,34,45,51\) have color pairs \(A\text{--}B,\ B\text{--}A,\ A\text{--}B,\ B\text{--}C,\ C\text{--}A\), respectively. The edges from \(6\) are \(16,26,36,46,56\), and their color pairs are \(A\text{--}D,\ B\text{--}D,\ A\text{--}D,\ B\text{--}D,\ C\text{--}D\). Thus every edge is properly colored and \(\chi(G)\le4\).
For the lower bound, the five cycle vertices cannot be colored with two colors, by the alternating-color contradiction in the preceding example. Therefore, any coloring of the whole graph using at most three colors must use all three colors on those five vertices. Vertex \(6\) is adjacent to every one of them, so it cannot use any of those three colors. A fourth color is necessary, and \(\chi(G)\ge4\).
Check: the four-coloring and the lower-bound argument match, giving \(\chi(G)=4\). Yet \(\omega(G)=3\): a clique containing \(6\) can include at most two cycle vertices, since among the cycle vertices no three are pairwise adjacent. A clique not containing \(6\) also has at most two vertices, for the same reason. The clique lower bound is therefore \(3\), strictly below the chromatic number; the cycle-plus-hub argument proves the stronger lower bound.
Common Mistakes and What a Certificate Does
Mistake: treating a coloring as proof of optimality. If a proper coloring uses three colors, the conclusion is \(\chi(G)\le3\), not \(\chi(G)=3\). The correction is to add a lower-bound argument ruling out one or two colors.
Mistake: treating the clique number as the chromatic number. A clique of size \(r\) proves only \(\chi(G)\ge r\). It does not prove \(\chi(G)\le r\), and the last example shows why equality cannot be assumed. To prove equality, supply an \(r\)-coloring as well, or establish a lower bound by another valid argument.
Mistake: checking only the proposed color classes informally. A single edge with both endpoints in the same class invalidates the claimed upper bound. In an edge-listed problem, check every listed edge. Conversely, an omitted edge can make an invalid coloring appear valid, so write the full edge set before checking.
A certificate is a proof, not necessarily a search procedure that finds an optimal coloring for every graph. The examples show how to certify a proposed answer once a useful coloring and lower-bound witness have been found. If the bounds do not match, the information so far does not determine the chromatic number: improve the coloring, strengthen the lower bound, or both.
Check Your Understanding
For each question, distinguish the upper-bound evidence from the lower-bound evidence.
- A graph has a proper coloring with four colors and contains a clique of size four. What is its chromatic number, and which fact proves each inequality?
- Explain why restricting a proper coloring of \(G\) to a subgraph \(H\) proves \(\chi(H)\le\chi(G)\).
- In the second worked example, why does alternating two colors around the cycle force vertices \(1\) and \(5\) to have the same color?
- What does a proper coloring with five colors prove about \(\chi(G)\), and what does it not prove by itself?
- Give a reason that the clique lower bound does not determine the chromatic number of the graph in the third worked example.