 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2007/a/2/d/solution

Choose the central vertex's color in

x

ways. Every rim vertex must avoid that color, so the rim is a cycle colored using the remaining

x - 1

colors. Hence

p_{W_{n + 1}} (x) = x ((x - 2)^{n} + (- 1)^{n} (x - 2)) .

 New to topics? Read the docs here!