Count colorings with a recurrence

Try

Counting colorings is more informative than asking only whether three colors suffice. A triangle has k(k−1)(k−2) proper colorings with k named colors. The labels on the colors matter: swapping red and blue usually creates a different coloring in this count. The resulting polynomial P_G(k) is the chromatic polynomial, and its smallest positive integer input with a positive value is the chromatic number for a nonempty graph.

Predict

Predict how removing an edge partitions the newly allowed colorings. If the endpoints still receive different colors, the coloring was already valid before deletion. If they receive the same color, merge those endpoints and count colorings of the contracted graph. This gives deletion–contraction. It is a classification of colorings, not an approximate recurrence based on graph size.

Experiment

Apply the recurrence to one edge of a triangle.

Graph	Coloring count
Edge deleted: three-vertex path	k(k−1)²
Edge contracted: two adjacent vertices	k(k−1)
Triangle: difference	k(k−1)(k−2)

The contraction can create parallel edges, but duplicate adjacency constraints do not change proper colorings. A loop, by contrast, makes every proper-coloring count zero.

Understand

For a nonloop edge e, every proper coloring of G−e either separates its endpoints or identifies their colors. The first class has size P_G(k); the second corresponds bijectively to proper colorings of G/e. Therefore P_G=P_(G−e)−P_(G/e). Starting from edgeless graphs, whose count is k^n, induction proves polynomiality. A tree rooted at one vertex has k choices at the root and k−1 at each remaining vertex, giving k(k−1)^(n−1). The recurrence also yields the cycle formula P_(C_n)(k)=(k−1)^n+(−1)^n(k−1), which can be checked inductively by deleting and contracting a cycle edge.

Apply

An alternative inclusion–exclusion formula sums over edge subsets F: P_G(k)=Σ_F(−1)^(size (F)) k^(c(F)), where c(F) is the number of components in the spanning subgraph with edge set F. Requiring every selected edge monochromatic forces each component to one color, explaining the exponent. For a simple n-vertex graph, the leading term is k^n and the next coefficient is minus the number of edges. A single selected edge reduces components by one; any two distinct edges reduce them by at least two. This gives a useful consistency check on a computed polynomial.

A computed polynomial should satisfy several independent checks: degree equals the vertex count, the leading coefficient is one, and P(1)=0 whenever an edge exists. For a graph with at least one edge, P(0)=0 as well. These are necessary checks, not a proof that every coefficient is correct; evaluate a small positive color count by direct enumeration to test the recurrence output.

Continue

The polynomial is an invariant under graph isomorphism but not a complete one: every tree on the same number of vertices has the same polynomial. Its values at nonpositive integers have other interpretations, but those require separate theorems and are not ordinary counts of colorings with negative colors. As a coding exercise, implement deletion–contraction with memoization and compare small results against exhaustive color assignments. State the exponential worst-case cost of the basic recursion rather than presenting it as an efficient general solution to graph coloring.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with use faces to certify planar obstructions.