Vollständiger Graph/Chromatisches Polynom/Beispiel

Es sei ${}G$ ein vollständiger Graph mit ${}n$ Knotenpunkten. Dann ist das chromatische Polynom gleich

$X(X-1)(X-2)\cdots (X-n+1).$

Bei ${}k\leq n-1$ Farben gibt es keine zulässige Färbung des vollständigen Graphen. Bei ${}k\geq n-1$ sind nur die injektiven Abbildungen

$f\colon V\longrightarrow \{1,\ldots ,k\}$

zulässige Färbungen. Davon gibt es nach Fakt ${}k(k-1)(k-2)\cdots (k-n+1)$ Stück.