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