Rundgang/Chromatisches Polynom/Aufgabe/Lösung


Für ist das chromatische Polynom nach Beispiel gleich

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