Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 2

For a positive integer $x$, the chromatic polynomial $p_G(x)$ counts proper vertex colorings from a palette of $x$ labelled colors, where adjacent vertices must have different colors. The counting function agrees with a polynomial, as proved by deletion-contraction in the next part.

For an edge $e=uv$, colorings of $G-e$ divide into those giving $u,v$ different colors, counted by $p_G$, and those giving them the same color, counted by $p_{G/e}$. Parallel edges produced by contraction may be suppressed. ThusFor an edgeless graph on $n\ge 1$ vertices, $p_G=x^n$. Induct on the number of edges, allowing smaller vertex counts for contractions. If both smaller expansions have alternating nonnegative coefficients, the contraction's leading degree is one lower, so subtracting it giveswith absent coefficients interpreted as zero. Each coefficient remains nonnegative. Both terms have zero constant coefficient for nonempty graphs, so the resulting expansion isThis induction simultaneously proves the counting function is a polynomial.

For a triangle, $p_{C_3}=x(x-1)(x-2)=(x-1{)}^3-(x-1)$. For $n\ge 4$, deleting an edge leaves a path with polynomial $x(x-1{)}^{n-1}$, and contracting it leaves $C_{n-1}$. Deletion-contraction and induction giveThe path formula chooses its first color freely and each succeeding color in $x-1$ ways.

Choose the central vertex's color in $x$ ways. Every rim vertex must avoid that color, so the rim is a cycle colored using the remaining $x-1$ colors. Hence