Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 17H / b / Solution

Factor the proposed polynomial:In particular,By the two-colourability criterion for bipartite graphs, every finite bipartite graph has at least one proper two-colouring, so its chromatic polynomial is positive at $2$. Therefore $f$ cannot be the chromatic polynomial of a bipartite graph.

It is nevertheless a chromatic polynomial. Start with the complete graph $K_3$, whose vertices may be coloured inways, and attach one leaf to any vertex. After the triangle is coloured, the leaf has $t-1$ available colours. The chromatic polynomial after attaching a leaf therefore gives

Solved by gpt-5.6-sol high.