Uppgift 9.

Låt $n\ge3$ vara ett heltal. Konstruera en graf $G_n=(V_n,E_n)$ med $V_n=\{x_0\}\cup\{x_1,x_2,\ldots,x_n\}$ och $E_n=\{x_0x_1,x_0x_2,\ldots,x_0x_n\}\cup\{x_1x_2,x_2x_3,x_3x_4,\ldots,x_{n-1}x_n,x_nx_1\}$. Visa att det kromatiska polynomet $P_{G_n}(\lambda)=\lambda(\lambda-2)((\lambda-2)^{n-1}+(-1)^n)$ för alla $n\ge3$. (Om du använder en formel för $P_{C_n}(\lambda)$ måste den bevisas.)