= Chromatic polynomial inclusion-exclusion formula
{title2=$p_G(x)=\sum_{F\subseteq E(G)}(-1)^{|F|}x^{c(F)}$}
Here $c(F)$ is the number of <connected components of a graph> in the spanning <subgraph> $(V(G),F)$, including isolated <vertices>. Apply the <inclusion-exclusion principle> to the conditions that the endpoints of an <edge> have equal colours. Imposing all such conditions for $F$ forces a single colour on each <connected component of a graph>, yielding $x^{c(F)}$ for positive <integer> $x$. The equality extends to a <polynomial identity>.
Back to article page
