Rundgang/Chromatisches Polynom/Aufgabe/Lösung

Für ${}n=3$ ist das chromatische Polynom nach Beispiel gleich

${}X(X-1)(X-2)=(X-1)(X^{2}-2X)=(X-1)((X-1)^{2}-1)=(X-1)^{3}-(X-1)\,,$

was den Induktionsanfang sichert. Es sei nun ${}G$ ein Rundgang mit ${}n\geq 4$ und sei die Aussage für kleinere Rundgänge bereits bekannt. Wir verwenden Fakt  (1) mit einer beliebigen Kante. Hierbei ist ${}G\setminus \{e\}$ ein linearer Graph mit ${}n$ Knoten und ${}G/e$ ist ein Rundgang mit ${}n-1$ Knoten, auf den wir die Induktionsvoraussetzung anwenden können. Somit ist unter Verwendung von Aufgabe das chromatische Polynom des Rundganges mit ${}n$ Knoten gleich

${}{\begin{aligned}X(X-1)^{n-1}-{\left((X-1)^{n-1}+(-1)^{n-1}(X-1)\right)}&=X(X-1)^{n-1}-(X-1)^{n-1}+(-1)^{n}(X-1)\\&={\left(X-1\right)}(X-1)^{n-1}+(-1)^{n}(X-1)\\&=(X-1)^{n}+(-1)^{n}(X-1).\end{aligned}}$

Zur gelösten Aufgabe