Chromatic Numbers of Complete Graphs

Coloring a Complete Graph

A complete graph places an edge between every pair of distinct vertices. This makes its coloring requirement especially direct: no two vertices can share a color. The key is to match that restriction with a coloring that uses no more colors than necessary. Together, these two checks determine the chromatic number exactly.

All graphs in this tutorial are finite and simple. A proper vertex coloring assigns a color to each vertex so that the endpoints of every edge receive different colors. A color may be represented by a label such as \(1\), \(2\), or \(3\); only whether labels agree or differ matters. The chromatic number, denoted \(\chi(G)\), is the smallest number of colors used in any proper coloring of \(G\).

For example, if \(V(K_4)=\{1,2,3,4\}\), then its edges are precisely \(12,13,14,23,24,34\). Each pair of distinct vertices appears as an edge. This property, rather than any particular drawing or vertex labels, drives the coloring argument.

The Clique Lower Bound

Proof. Consider any proper coloring of \(G\), and let \(S\) be a clique with \(r\) vertices. Every two distinct vertices of \(S\) are adjacent. By properness, adjacent vertices receive different colors, so all \(r\) vertices of \(S\) must receive pairwise different colors. The coloring therefore uses at least \(r\) colors. This holds for every proper coloring, so the minimum number of colors satisfies \(\chi(G)\ge r\). \(\square\)

This is a lower bound: it says that fewer than \(r\) colors cannot work. By itself, it does not show that \(r\) colors suffice. To determine a chromatic number exactly, we also need an upper bound, usually supplied by exhibiting a proper coloring with the required number of colors.

The Chromatic Number of \(K_n\)

Proof. Fix a positive integer \(n\). Since every pair of distinct vertices of \(K_n\) is adjacent, its \(n\) vertices form a clique. The clique lower bound gives \(\chi(K_n)\ge n\).

For the reverse inequality, assign a different color to each vertex. This uses \(n\) colors. Every edge has two distinct endpoints, and those endpoints were assigned different colors, so this is a proper coloring. Hence \(\chi(K_n)\le n\). Combining the two inequalities gives \(\chi(K_n)=n\). The argument includes \(n=1\): there is one vertex, no edge to violate properness, and one color suffices; the clique lower bound requires at least one. \(\square\)

There is another way to understand the upper-bound construction. In any proper coloring of a complete graph, each color class contains at most one vertex: if a color appeared on two distinct vertices, the edge between them would have equal-colored endpoints. Thus \(n\) vertices require at least \(n\) nonempty color classes. Giving each vertex its own color achieves exactly that number. The clique argument expresses the same restriction as a general lower bound that can also be used in graphs that are not complete.

Why the Two Bounds Matter

A coloring with \(n\) colors proves only that \(\chi(K_n)\le n\). It does not rule out the possibility that some different coloring uses fewer colors. The clique lower bound supplies precisely that missing argument: because every pair of vertices is adjacent, no two vertices can share a color. The complete graph's chromatic number is exact because the lower and upper bounds meet.

This proof pattern is useful beyond complete graphs. For any graph, a clique of size \(r\) certifies that at least \(r\) colors are needed; a separate coloring may show that \(r\) colors suffice. If both statements hold, the chromatic number is \(r\). In \(K_n\), the whole vertex set is already a clique, and assigning each vertex its own color provides the matching coloring.

Common Pitfall: A Proposed Coloring Must Check Every Edge

Consider \(K_4\) with the vertex and edge sets from the worked example. A tempting but incorrect calculation is to use three colors by assigning red to \(1\) and \(4\), blue to \(2\), and green to \(3\). The edges \(12,13,23,24,34\) have differently colored endpoints, but the edge \(14\) has red at both endpoints. Since \(14\in E(K_4)\), this assignment is not a proper coloring and cannot establish \(\chi(K_4)\le3\).

The correction is to check every edge in the specified edge set, not just a selection of edges. In \(K_4\), every pair is adjacent, so the clique lower bound already gives \(\chi(K_4)\ge4\); a three-coloring is impossible. Assigning four distinct colors is proper, so \(\chi(K_4)=4\).

For the empty graph on no vertices, some conventions write \(K_0\) and define its chromatic number to be \(0\): the empty assignment is a proper coloring using no colors, and no number of colors can be smaller than \(0\). The theorem above is stated for positive \(n\), which avoids relying on a convention for \(K_0\); if this convention is adopted, the same numerical formula extends to \(n=0\).