= Solution
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 as
$$
p_G(x)=p_H(x)+p_{H/e}(x).
$$
The 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 \b[$p_G(x)>0$ for all $x>n-1$], including noninteger $x$; counting colorings alone would not establish that real-variable claim.
Back to article page
