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

For a finite simple loopless graph, $p_G(q)$ counts proper vertex colorings with $q$ labelled available colors, initially for nonnegative integer $q$. For an edge $e=uv$, proper colorings of $G-e$ split into those with different endpoint colors, counted by $p_G(q)$, and those with equal endpoint colors, counted by the contracted graph. Hence the deletion-contraction recurrence for the chromatic polynomial isParallel edges created by contraction can be suppressed since they impose the same coloring constraint. A graph with no edges has $p_G(q)=q^{|V(G)|}$. Induction by this recurrence therefore gives a polynomial agreeing with the counting function on all nonnegative integers. That polynomial is unique because two distinct polynomials cannot agree at infinitely many points.

Induct using the same deletion-contraction recurrence for the chromatic polynomial. The edgeless graph has polynomial $x^n$, so its leading coefficient is one and the others are zero. All nonempty-vertex chromatic polynomials have zero constant term, since no coloring uses zero colors.

For an existing edge, write the alternating coefficient lists of the deletion and simplified contraction as $a_i^{\prime }$ and $a_i^{\prime \prime }$. The contraction has $n-1$ vertices, so subtracting its polynomial changes its leading sign by one place. Thuswith nonexistent indices understood as zero. Both summands are nonnegative by induction. The leading coefficient is $a_0=1$, and the next isThis proves the alternating expansion and nonnegativity of every $a_i$. The coefficient assertion for $a_1$ is relevant when $n\ge 2$; the one-vertex graph simply has polynomial $x$.

Set $t=-x>0$. The coefficient formula givesEvery summand is nonnegative and the leading term is $t^n>0$, since $a_0=1$. Therefore

For the complete graph, $p_{K_n}(x)=x(x-1)\cdots (x-n+1)>0$ whenever $x>n-1$.

Use induction on the number of vertices, and for fixed $n$ on the number of missing edges. If $G$ is not complete, choose a missing edge $e$ and put $H=G+e$. The recurrence rearranges asThe first term is positive by the missing-edge induction. The second graph has $n-1$ vertices, so the vertex induction makes its polynomial positive for $x>n-2$, in particular for the present range. The one-vertex base case is $x>0$. Thus $p_G(x)>0$ for all $x>n-1$, including noninteger $x$; counting colorings alone would not establish that real-variable claim.