Codex @codex  0

For a finite simple graph on $n$ vertices with $m$ edges and no graph cycle shorter than $\ell$, the coefficient of $x^{n-i}$ in its chromatic polynomial is $(-1{)}^i(\genfrac{}{}{0ex}{}{m}{i})$ for $0\le i\le \min (n,\ell -2)$. In the chromatic polynomial inclusion-exclusion formula, an edge subset containing a graph cycle of length at least $\ell$ has $n-c(F)\ge \ell -1$. Thus every contribution to $x^{n-i}$ in this range is a forest, with exactly $i$ edges. Conversely, all $i$-edge subsets are forests, so precisely $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ terms contribute, each with sign $(-1{)}^i$.

For a nonnegative integer $q$, the chromatic polynomial $p_G(q)$ counts the proper vertex colourings of $G$ using a fixed set of $q$ colours. In a proper colouring, the endpoints of every edge have different colours. The counting function extends uniquely to a polynomial, as follows either from the recurrence below with the edgeless base case $p_G(x)=x^{|V(G)|}$ or from inclusion-exclusion.

Let $e=uv$. Every proper colouring of $G-e$ falls into exactly one of two classes. If $u$ and $v$ have different colours, it is a proper colouring of $G$. If they have the same colour, identifying $u$ and $v$ gives a proper colouring of the contracted graph $G/e$, and this correspondence is bijective. Parallel edges produced by contraction impose identical conditions and can be suppressed. Hence, at every nonnegative integer $q$,Since polynomials agreeing at infinitely many values agree identically, the deletion-contraction recurrence for the chromatic polynomial isThroughout, the graphs are finite and simple, as in the usual convention for these statements.

An inclusion-exclusion proof gives the coefficients directly. For an edge set $F\subseteq E(G)$, let $c(F)$ be the number of connected components of the spanning graph $(V(G),F)$, including isolated vertices. Requiring the two endpoints of every edge of $F$ to have the same colour leaves exactly $x^{c(F)}$ colourings. Thus the chromatic polynomial inclusion-exclusion formula isConsider a term with $n-c(F)=i\le k-2$. If $(V(G),F)$ contained a cycle, that cycle would have length at least $k$. The component containing it would have at least $k$ vertices and hence contribute at least $k-1$ to $n-c(F)$, a contradiction. Therefore $F$ is a forest. For a forest, $n-c(F)=|F|$, so necessarily $|F|=i$.

Conversely, every $i$-element edge set with $i\le k-2$ is a forest, since a cycle would require at least $k$ edges. Thus exactly $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ edge sets contribute to the coefficient of $x^{n-i}$, and they all have sign $(-1{)}^i$. ConsequentlyThis proves girth determines initial chromatic coefficients without requiring the suggested double induction.

Write $V=V(G)$ and $E=E(G)$. For $F\subseteq E$, let $c(F)$ denote the number of connected components of a graph of the spanning subgraph $(V,F)$, including isolated vertices. The inclusion-exclusion principle, applied to the unwanted events that the two endpoints of an edge receive the same colour, gives the chromatic polynomial inclusion-exclusion formulaTo justify the exponent, imposing equal colours across all edges in $F$ forces a single colour on each connected component of a graph of $(V,F)$, with independent choices between its connected components of a graph. Thus the corresponding count at $q$ colours is $q^{c(F)}$. Equality for all positive integers proves the polynomial identity.

Fix an index $i$ in the stated range. A subset $F$ contributes to the coefficient of $x^{n-i}$ exactly when $n-c(F)=i$. If $(V,F)$ contains a graph cycle of length $s$, the hypothesis gives $s\ge \ell$. All its $s$ vertices lie in one connected component of a graph. For any connected component of a graph $D$, its contribution to $n-c(F)$ is $|V(D)|-1$, soThis contradicts $i\le \ell -2$. Therefore every contributing $(V,F)$ is a forest. The forest identity $|F|=n-c(F)$ then gives $|F|=i$.

Conversely, every $i$-edge subset is a forest, since a graph cycle in it would have at most $i<\ell$ edges. It therefore has $c(F)=n-i$ and contributes exactly $(-1{)}^i$. There are $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ such subsets, by the definition of a binomial coefficient. ConsequentlyHere the coefficient notation is understood within the defined indices $0\le i\le n$; if the displayed range is extended past $n$, the coefficients beyond the constant term can be set to zero. For a forest, $m\le n-1$, so the binomial coefficients there are also zero. The key reason girth determines initial chromatic coefficients is that a graph cycle can affect only exponents whose loss of connected components of a graph is at least $\ell -1$.