= Chromatic polynomial after attaching a leaf
Attaching a new <vertex> that is a <leaf of a graph> multiplies the <chromatic polynomial> by $t-1$: after colouring the old graph, the new <vertex> may receive any colour except its neighbour's. Starting with one <vertex> and repeatedly adding a <leaf of a graph> constructs any finite <tree>. Thus a <tree> with $n\geq 1$ <vertices> has
$$
P_T(t)=t(t-1)^{n-1}.
$$
In contrast, every pair of <vertices> in a <complete graph> must receive different colours, so the <multiplication principle> gives the <falling factorial>
$$
P_{K_n}(t)=t(t-1)\cdots(t-n+1).
$$
For positive <integers> $t<n$ this product vanishes, expressing the impossibility of assigning distinct colours to all $n$ <vertices>.
Back to article page
