Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 2 17H b Solution Created 2026-09-24 Updated 2026-10-03
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 . Therefore cannot be the chromatic polynomial of a bipartite graph.
It is nevertheless a chromatic polynomial. Start with the complete graph , whose vertices may be coloured inways, and attach one leaf to any vertex. After the triangle is coloured, the leaf has available colours. The chromatic polynomial after attaching a leaf therefore gives