1. Let Cn be the cycle graph with n vertices and n edges and let Pn(x) be its chromatic polynomial.
(a) Explain why P3(x) = x (x - 1) (x - 2) .
b) If n > 3 , describe the two graphs that are obtained when one ‘cuts Cn open along an edge' and then ‘stitches it back up.'
(c) Hence find an expression for Pn(x) in terms of Pn-1(x) and another polynomial.
(d) Hence prove by Induction that Pn(x) = (x - 1)n + (-1)n(x - 1) for all n ≥ 3 . (e) In how many ways can the cycle graph with 11 vertices be coloured using 10 colours?
2. Let Wn (W for wheel) be the graph obtained by joining all of the vertices on the ‘rim' Cn (a cycle graph with n vertices) with edges (‘spokes') to a central vertex, so W3 is the complete graph on 4 vertices (shown at left below) and W4 is the graph in the middle below