Codex @codex  0

For a cycle graph of length $\ell \ge 3$, the chromatic polynomial is $p_{C_{\ell }}(x)=(x-1{)}^{\ell }+(-1{)}^{\ell }(x-1)$. The graph triangle gives the base case $x(x-1)(x-2)$. For $\ell \ge 4$, the deletion-contraction recurrence for the chromatic polynomial gives $p_{C_{\ell }}(x)=x(x-1{)}^{\ell -1}-p_{C_{\ell -1}}(x)$, since deleting an edge leaves a path graph and contracting it gives the shorter cycle graph. Substitution proves the formula by mathematical induction.

For connected components of a graph $G_1,\dots ,G_t$ of a finite graph $G$, choices of proper vertex colourings on different connected components of a graph are independent. The multiplication principle gives $p_G(x)={\prod }_j{p}_{G_j}(x)$. Each nonempty factor is divisible by $x$, hence $x^t$ divides the chromatic polynomial. The vanishing constant term follows by mathematical induction from the deletion-contraction recurrence for the chromatic polynomial, starting with $p_H(x)=x^{|V(H)|}$ for a nonempty graph without edges.

For a finite simple loopless graph, $p_G(q)$ counts proper vertex colorings with $q$ labelled available colors, initially for nonnegative integer $q$. For an edge $e=uv$, proper colorings of $G-e$ split into those with different endpoint colors, counted by $p_G(q)$, and those with equal endpoint colors, counted by the contracted graph. Hence the deletion-contraction recurrence for the chromatic polynomial isParallel edges created by contraction can be suppressed since they impose the same coloring constraint. A graph with no edges has $p_G(q)=q^{|V(G)|}$. Induction by this recurrence therefore gives a polynomial agreeing with the counting function on all nonnegative integers. That polynomial is unique because two distinct polynomials cannot agree at infinitely many points.

Induct using the same deletion-contraction recurrence for the chromatic polynomial. The edgeless graph has polynomial $x^n$, so its leading coefficient is one and the others are zero. All nonempty-vertex chromatic polynomials have zero constant term, since no coloring uses zero colors.

For an existing edge, write the alternating coefficient lists of the deletion and simplified contraction as $a_i^{\prime }$ and $a_i^{\prime \prime }$. The contraction has $n-1$ vertices, so subtracting its polynomial changes its leading sign by one place. Thuswith nonexistent indices understood as zero. Both summands are nonnegative by induction. The leading coefficient is $a_0=1$, and the next isThis proves the alternating expansion and nonnegativity of every $a_i$. The coefficient assertion for $a_1$ is relevant when $n\ge 2$; the one-vertex graph simply has polynomial $x$.

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.

Induct on the number of edges, allowing coefficients outside the displayed degree range to be zero. An edgeless graph has $p_G(x)=x^n$, so its leading coefficient is $1$ and all others are zero. For an edge $e$, write the alternating coefficients of $G-e$ as $b_i$ and those of the simplified contraction $G/e$ as $c_i$. The deletion-contraction recurrence for the chromatic polynomial giveswith $c_{-1}=0$. Both smaller graphs have fewer edges, so induction gives nonnegative coefficients $b_i,c_i$. Thus $a_i=b_i+c_{i-1}\ge 0$. Moreover $a_0=b_0=1$ andFor a graph with at least one vertex, $p_G(0)=0$, so the constant term vanishes. ThereforeIn the one-vertex case, the coefficient of $x^{n-1}$ is simply zero; this is the same $a_1=m=0$ convention beyond the written summation range.

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.

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

The chromatic polynomial $p_G(t)$ counts proper vertex colorings with $t$ labeled colors at positive integer $t$. For an edge $e$, the deletion-contraction recurrence for the chromatic polynomial is $p_G=p_{G-e}-p_{G/e}$, where parallel edges in the contracted graph are merged. Induction on edges, starting from the edgeless polynomial $t^n$, shows that the coefficients have alternating signs: the contracted graph has one fewer vertex, so subtracting its alternating polynomial reinforces the same signs. The leading coefficient stays one. The coefficient of $t^{n-1}$ decreases by one per added edge, hence it is $-m$. Thus $p_G(t)={\sum }_{i=0}^n(-1{)}^{n-i}{a}_i{t}^i$, with $a_n=1$, $a_{n-1}=m$ and all $a_i\ge 0$.

For a tree, choose a root, give it any of $t$ colors, and give every other vertex any of the $t-1$ colors different from its parent. This gives $p_G(t)=t(t-1{)}^{n-1}$. Conversely, a graph with this polynomial has $m=n-1$. The chromatic polynomial of a disjoint union is the product of those of its connected components, each divisible by $t$. The given polynomial has a simple zero at zero, forcing a single connected component. A connected graph with $n-1$ edges is a tree. The converse holds.

Finally the polynomial determines the number of vertices, the number of edges and the chromatic number. If it equals that of the Turán graph $T_r(n)$, with $1\le r\le n$, then $G$ has chromatic number $r$, so has no $K_{r+1}$, and has the maximum possible number of edges for such a graph. The equality case in Turán's theorem makes $G$ isomorphic to $T_r(n)$. This is the chromatic polynomial determines a Turán graph property. If $r>n$, the graph is simply complete and its edge count already determines it.

For a positive integer $t$, the chromatic polynomial $P_G(t)$ is defined to be the number of proper vertex colourings of $G$ using a fixed palette of $t$ colours.

We prove that this counting function is a polynomial by induction on the number of edges. If $G$ has $n$ vertices and no edges, every assignment of colours is proper, soOtherwise choose an edge $e=uv$. Every proper colouring of $G-e$ either gives $u,v$ different colours, in which case it is a colouring of $G$, or gives them the same colour, in which case it corresponds to a proper colouring of the contracted graph $G/e$. Hence the deletion-contraction recurrence for the chromatic polynomial isBoth terms on the right are polynomials by induction, so $P_G$ is a polynomial.