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

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.