= Chromatic polynomial of a cycle
{title2=$p_{C_\ell}(x)=(x-1)^\ell+(-1)^\ell(x-1)$}
For a <cycle graph> of length $\ell\geq3$, the <chromatic polynomial> is $p_{C_\ell}(x)=(x-1)^\ell+(-1)^\ell(x-1)$. The <graph triangle> gives the base case $x(x-1)(x-2)$. For $\ell\geq4$, the <deletion-contraction recurrence for the chromatic polynomial> gives $p_{C_\ell}(x)=x(x-1)^{\ell-1}-p_{C_{\ell-1}}(x)$, since deleting an <edge> leaves a <path graph> and contracting it gives the shorter <cycle graph>. Substitution proves the formula by <mathematical induction>.
Back to article page
