Complete Graphs and Falling Factorials

Why Complete Graphs Give Falling Factorials

In a complete graph, every pair of distinct vertices is adjacent. A proper coloring therefore has to give every vertex a different color. This makes the coloring count especially direct: choose a color for the first vertex, then a color not already used for the second, and continue. The resulting product is a falling factorial.

For a finite simple graph \(G\), a proper coloring with \(q\) colors is a function from \(V(G)\) to a set of \(q\) labeled colors such that adjacent vertices receive different colors. The chromatic polynomial \(P_G(q)\) is the polynomial whose value at each nonnegative integer \(q\) counts those proper colorings. The color labels matter: swapping two labels generally gives a different coloring.

We will derive the formula for every \(n\ge0\). The empty graph \(K_0\) is included because it has exactly one coloring: the empty function. Its chromatic polynomial is the constant \(1\), consistent with the empty-product convention.

Deriving the Formula

Proof. First suppose \(n\ge1\), and let \(q\) be a nonnegative integer. Every two distinct vertices of \(K_n\) are adjacent, so in a proper coloring all \(n\) vertices must receive different colors.

If \(q\ge n\), process the vertices in the order \(1,2,\ldots,n\). Vertex \(1\) has \(q\) choices. After the first \(i-1\) vertices have received distinct colors, vertex \(i\) has \(q-(i-1)\) choices, because it cannot use any of those \(i-1\) colors. Multiplying the numbers of choices gives \(q(q-1)\cdots(q-n+1)=q^{\underline n}\).

If \(0\le q<n\), there are not enough colors to assign a different one to each of the \(n\) vertices, so there are no proper colorings. In the product \(q(q-1)\cdots(q-n+1)\), the factor \(q-q=0\) occurs: it is the factor corresponding to the \((q+1)\)-st term. Thus the product is also zero. This includes \(q=0\), for which the first factor is zero when \(n\ge1\).

For \(n=0\), there is one empty coloring for every nonnegative integer \(q\), and \(q^{\underline 0}=1\). We have therefore shown that the polynomial \(q^{\underline n}\) agrees with the coloring count for every nonnegative integer \(q\). Two polynomials agreeing at infinitely many values are identical: their difference would otherwise be a nonzero polynomial with infinitely many roots, which is impossible because a nonzero polynomial of degree \(d\) has at most \(d\) roots. Hence \(P_{K_n}(q)=q^{\underline n}\). \(\square\)

The sequential choice argument directly counts colorings when \(q\ge n\). When \(q<n\), it is important not to interpret later negative factors as numbers of available colors. The count is zero because there are too few colors; the product is zero because it contains a zero factor.

Worked Evaluations

Roots and What They Mean

For \(n\ge1\), the formula factors as \(P_{K_n}(q)=q(q-1)\cdots(q-n+1)\). Therefore its roots are exactly \(0,1,\ldots,n-1\). Each is a root because one factor vanishes at that value. There are no other roots: if the product is zero, at least one of its factors must be zero, and that forces \(q\) to equal one of those integers. The factors are distinct, so each listed root occurs once.

For nonnegative integer inputs, these roots have a direct counting interpretation. A palette with fewer than \(n\) colors cannot give distinct colors to all \(n\) vertices, so the number of proper colorings is zero. In particular, \(P_{K_n}(0)=0\) for \(n\ge1\), while \(P_{K_0}(0)=1\) because the empty function is the only coloring of the empty vertex set.

The polynomial can also be evaluated at non-integer or negative values, but those evaluations do not count colorings: a palette size must be a nonnegative integer. For instance, the formula gives \(P_{K_2}(-1)=(-1)(-2)=2\). This is a valid polynomial evaluation, not a coloring count.

A Common Counting Mistake

A common error is to treat every vertex after the first as having the same number of choices. For example, one might incorrectly write \(P_{K_4}(3)=3\cdot2^3=24\), reasoning that each later vertex has two colors other than the first vertex’s color. This ignores the requirement that the later vertices must also avoid each other’s colors.

The correct sequential count begins with three choices for vertex \(1\), then \(3-1=2\) choices for vertex \(2\). Vertex \(3\) must avoid two used colors, leaving \(3-2=1\) choice; vertex \(4\) must avoid three used colors, leaving \(3-3=0\) choices. Thus \(P_{K_4}(3)=3\cdot2\cdot1\cdot0=0\). The zero is necessary: a proper coloring would require four distinct colors, but only three are available.

The formula is useful precisely because it records how the number of available colors changes at each step. It also makes the complete graph’s coloring threshold visible: at least \(n\) colors are needed to color \(K_n\), and for \(q\ge n\) the falling factorial counts every labeled proper coloring.