= Solution
{c}
Let the nonempty <connected components of a graph> of $G$ be $G_1,\ldots,G_t$. A <proper vertex colouring> can be chosen separately on each <connected component of a graph>, since no <edge> joins different <connected components of a graph>. The <multiplication principle> gives, first at positive <integers> and then as a <polynomial identity>,
$$
p_G(x)=\prod_{j=1}^t p_{G_j}(x).
$$
It remains to justify that every factor has zero constant term. More generally, for every nonempty <simple graph> $H$, prove $p_H(0)=0$ by <mathematical induction> on the number of <edges>. If there are no <edges>, then $p_H(x)=x^{|V(H)|}$ with $|V(H)|\geq1$. Otherwise choose an <edge> $e$. Both $H-e$ and the simplified <edge contraction> $H/e$ are nonempty <graphs> with fewer <edges>. The <deletion-contraction recurrence for the chromatic polynomial> and <mathematical induction> give
$$
p_H(0)=p_{H-e}(0)-p_{H/e}(0)=0.
$$
Thus $p_{G_j}(x)=xq_j(x)$ for a <polynomial> $q_j$, and
$$
\boxed{p_G(x)=x^t\prod_{j=1}^t q_j(x),\qquad x^t\mid p_G(x).}
$$
For the empty <graph>, $t=0$ and $p_G(x)=1$, so the conclusion also holds. This is the <chromatic polynomial product over components>.
Back to article page
