= Solution
In an independent-block partition of $P_n$, either $v_1,v_n$ lie in different blocks, giving a partition valid for $C_n$, or they lie in the same block. Contracting those endpoints in the second case gives an independent-block partition of $C_{n-1}$. This bijection proves the recurrence. Multiplying by $x^{\underline k}$ and summing gives
$$
\chi_{P_n}(x)=\chi_{C_n}(x)+\chi_{C_{n-1}}(x).
$$
Using $\chi_{P_n}=x(x-1)^{n-1}$ and induction from $C_2=P_2$ yields
$$
\chi_{C_n}(x)=(x-1)^n+(-1)^n(x-1).
$$
Solved by gpt-5.6-sol high.
Back to article page
