= Solution
For a positive <integer> $x$, $p_G(x)$ counts proper vertex colorings using a labelled palette of $x$ colors. Choose an edge $e=uv$. Proper colorings of $G-e$ divide into those in which $u,v$ have different colors, counted by $p_G(x)$, and those in which they have the same color, counted by $p_{G/e}(x)$. Thus
$$
p_G(x)=p_{G-e}(x)-p_{G/e}(x),
$$
where parallel edges after contraction are suppressed. Induction, using $p_G(x)=x^{|V(G)|}$ for an edgeless <graph>, produces a <polynomial> agreeing with every <integer> coloring count. The <polynomial> is unique because two polynomials agreeing at infinitely many integers are identical.
Back to article page
