Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 2 / c

For a triangle, $p_{C_3}=x(x-1)(x-2)=(x-1{)}^3-(x-1)$. For $n\ge 4$, deleting an edge leaves a path with polynomial $x(x-1{)}^{n-1}$, and contracting it leaves $C_{n-1}$. Deletion-contraction and induction giveThe path formula chooses its first color freely and each succeeding color in $x-1$ ways.