Past exam of the graph theory course of the University of Oxford / 2023 / 2

For a finite graph $G$, its chromatic polynomial $p_G(x)$ is the polynomial whose value at each positive integer $q$ counts proper vertex colourings of $G$ from a fixed palette of $q$ labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.

For an edge $e=uv$, the deletion-contraction recurrence for the chromatic polynomial isHere $G-e$ deletes only the edge $e$, while $G/e$ performs edge contraction, identifying $u,v$ and removing $e$. Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.

Indeed, the proper vertex colourings of $G-e$ in which $u,v$ differ are precisely those of $G$, while those in which $u,v$ agree correspond bijectively to proper vertex colourings of $G/e$. This proves the equality for every positive integer $q$, hence as a polynomial identity. Together with $p_G(x)=x^{|V(G)|}$ for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.

Let the nonempty connected components of a graph of $G$ be $G_1,\dots ,G_t$. A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph $H$, prove $p_H(0)=0$ by mathematical induction on the number of edges. If there are no edges, then $p_H(x)=x^{|V(H)|}$ with $|V(H)|\ge 1$. Otherwise choose an edge $e$. Both $H-e$ and the simplified edge contraction $H/e$ are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction giveThus $p_{G_j}(x)=x{q}_j(x)$ for a polynomial $q_j$, andFor the empty graph, $t=0$ and $p_G(x)=1$, so the conclusion also holds. This is the chromatic polynomial product over components.

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$.

First reduce the unicyclic graph to its unique graph cycle $C$. Delete the edges of $C$ but retain every vertex. The remaining graph is a forest, since any surviving graph cycle would be a second one in $G$. Each of its connected components of a graph contains a vertex of $C$: follow a graph path to $C$ in the original connected graph, stopping at the first vertex of $C$; this initial segment uses no edge of $C$.

No such connected component of a graph contains two vertices of $C$. Otherwise, on the tree graph path between them, choose two successive visits to $C$. The segment between these visits has no internal vertex on $C$ and uses no edge of $C$. Combining it with either connecting arc of $C$ gives a second graph cycle, a contradiction. Thus the remaining graph consists of trees, each rooted at exactly one vertex of $C$.

After choosing a proper vertex colouring of $C$ from $q$ colours, colour these rooted trees away from their roots. Each of the $n-\ell$ off-graph cycle vertices has one already coloured parent in a rooted tree, leaving exactly $q-1$ choices. The multiplication principle therefore givesEquivalently, this repeatedly applies the chromatic polynomial after attaching a leaf formula.

To compute the chromatic polynomial of a cycle, the base case is the graph triangle:For $s\ge 4$, deleting a cycle graph edge gives a path graph on $s$ vertices, while edge contraction gives $C_{s-1}$. The chromatic polynomial of that path graph is $x(x-1{)}^{s-1}$, by choosing the colour of its first vertex and then each successive vertex. Hence the deletion-contraction recurrence for the chromatic polynomial givesUsing mathematical induction, substitute $p_{C_{s-1}}(x)=(x-1{)}^{s-1}+(-1{)}^{s-1}(x-1)$ to obtainMultiplying by the factor for the attached trees proves the chromatic polynomial of a unicyclic graph formula