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.


Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 2 / e / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-145/2/e/solution