Låt $n \geq 3$ vara ett heltal. Konstruera en graf $G_{n} = (V_{n}, E_{n})$ med

V _ {n} = \left\{x _ {0} \right\} \cup \left\{x _ {1}, x _ {2}, \dots , x _ {n} \right\}

och

E _ {n} = \left\{x _ {0} x _ {1}, x _ {0} x _ {2}, \dots , x _ {0} x _ {n} \right\} \cup \left\{x _ {1} x _ {2}, x _ {2} x _ {3}, x _ {3} x _ {4}, \dots , x _ {n - 1} x _ {n}, x _ {n} x _ {1} \right\}.

Visa att det kromatiska polynomet $P_{G_n}(\lambda) = \lambda (\lambda - 2) ((\lambda - 2)^{n-1} + (-1)^n)$ för alla $n \geq 3$ . (Om du använder en formel för $P_{C_n}(\lambda)$ måste den bevisas.) (5 p)

FIGUR 1. Grafen $G_{9}$ från uppgift 9