Computing Polynomials by Deletion and Contraction

From a Graph to a Polynomial

A chromatic polynomial packages the number of proper colorings of a graph into an algebraic expression. Deletion and contraction turn that count into smaller graph counts. The practical skill is to choose an edge, keep the two resulting terms straight, and continue until the graphs are simple enough to count directly. Each step reduces the graph, so a recurrence tree gives a finite computation.

All graphs in this tutorial are finite and simple unless a contraction temporarily creates parallel edges. A proper coloring with $q$ colors assigns a color to every vertex so that adjacent vertices receive different colors. For a graph $G$, its chromatic polynomial $P_G(x)$ is the polynomial whose value at each positive integer $q$ is the number of proper $q$-colorings of $G$. We use the conventions $P_G(x)=0$ if $G$ has a loop, and that parallel edges impose just one constraint: their endpoints must have different colors. Thus parallel edges can be replaced by one edge without changing the polynomial.

Definition: If $e=uv$ is an edge of $G$, then $G-e$ is the graph obtained by deleting $e$. The contraction $G/e$ identifies $u$ and $v$ as one vertex, removes the edge $e$, and retains the adjacencies to other vertices. If this creates parallel edges, they may be suppressed to a single edge for chromatic-polynomial calculations.

The base case for a recursive calculation is an edgeless graph. With $n$ vertices, each vertex can be colored independently, so there are $q^n$ colorings and $P_G(x)=x^n$. This includes the graph with no vertices, whose one empty coloring gives polynomial $1=x^0$.

The Deletion–Contraction Rule

Theorem (Deletion–Contraction): If $e$ is a non-loop edge of $G$, then $$ P_G(x)=P_{G-e}(x)-P_{G/e}(x). $$

Proof. Fix a positive integer $q$ and count proper $q$-colorings. A proper coloring of $G-e$ either gives different colors to $u$ and $v$, or gives them the same color. The first class is exactly the set of proper colorings of $G$, because adding $e$ rules out precisely colorings in which its endpoints agree. The second class is in bijection with the proper colorings of $G/e$: a coloring in that class assigns a single common color to the contracted vertex, and all other edge constraints are exactly those of the contracted graph. Therefore the number of colorings of $G$ equals the number for $G-e$ minus the number for $G/e$. This holds for every positive integer $q$, so the corresponding chromatic polynomials satisfy the identity. $\square$

The subtraction is essential: $G-e$ allows the endpoint-equal colorings, while $G$ does not. A loop is not eligible for this rule; its graph already has polynomial zero. Each valid step reduces the edge count: deletion removes one edge, and contraction removes $e$, with any resulting parallel edges suppressed. Thus repeated application eventually reaches edgeless graphs or graphs with loops. The resulting recurrence tree is a calculation, not a guess: every branch uses the same counting identity, and every leaf uses a base case or the loop convention.

Worked Computations

Worked Example: The Triangle

Let $G=(V,E)$ have $V=\{1,2,3\}$ and $E=\{12,23,13\}$. Choose $e=12$. Deleting $12$ leaves the path with edges $13,23$; contracting $12$ leaves a single edge between the merged vertex and $3$.

First compute the path on three vertices. For that graph, delete edge $13$: the result has the single edge $23$ and isolated vertex $1$; contracting $13$ leaves a single edge between the merged vertex and $2$. A single edge has polynomial $x^2-x$, since its first endpoint has $x$ choices and the second has $x-1$. The graph with one edge and one isolated vertex has polynomial $x(x^2-x)=x^3-x^2$. Hence the path has polynomial $ (x^3-x^2)-(x^2-x)=x^3-2x^2+x$.

The contraction of $12$ in the original triangle is a single edge, with polynomial $x^2-x$. Therefore $P_G(x)=(x^3-2x^2+x)-(x^2-x)=x^3-3x^2+2x$.

Check: For $q=3$, the expression gives $27-27+6=6$. Directly, the three vertices of a triangle must all receive different colors, giving $3\cdot2\cdot1=6$ colorings.

Worked Example: A Four-Cycle

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,41\}$. Choose edge $12$. Deleting it leaves the path $2,3,4,1$. Contracting it identifies $1$ and $2$; the remaining edges form a triangle on the merged vertex, $3$, and $4$.

The path on four vertices can be computed by deleting its terminal edge. Deletion leaves a path on three vertices and an isolated vertex, so its polynomial is $x(x^3-2x^2+x)=x^4-2x^3+x^2$. Contraction leaves the path on three vertices, with polynomial $x^3-2x^2+x$. Subtracting gives the path-on-four-vertices polynomial $(x^4-2x^3+x^2)-(x^3-2x^2+x)=x^4-3x^3+3x^2-x$.

The contracted graph is the triangle computed above, with polynomial $x^3-3x^2+2x$. Applying deletion–contraction to the four-cycle gives \[ P_G(x)=(x^4-3x^3+3x^2-x)-(x^3-3x^2+2x) =x^4-4x^3+6x^2-3x. \]

Check: At $q=3$, the polynomial gives $81-108+54-9=18$. Independently, choose the color of vertex $1$ in $3$ ways and vertex $2$ in $2$ ways. If vertex $3$ has the same color as vertex $1$, there are $1$ choice for vertex $3$ and $2$ choices for vertex $4$, giving $3\cdot2\cdot1\cdot2=12$. If vertex $3$ has the third color, there is $1$ choice for vertex $3$, and vertex $4$ has $2$ choices, giving $3\cdot2\cdot1\cdot2=12$—but this would count 24, so we must distinguish the cases correctly: after fixing vertices $1,2$, vertex $3$ has two choices. One is the color of $1$, then vertex $4$ has two choices; the other is the third color, then vertex $4$ has only one choice (it must differ from both $1$ and $3$). Thus the count is $3\cdot2\cdot(2+1)=18$, agreeing with the polynomial.

Worked Example: A Four-Cycle with a Chord

Let $H=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,41,13\}$. Choose the chord $13$. Deleting it leaves the four-cycle, whose polynomial is $x^4-4x^3+6x^2-3x$. Contracting it identifies $1$ and $3$. The remaining edges $12,23,34,41$ become two edges from the merged vertex to $2$, and two from it to $4$. Suppressing the parallel copies leaves a path on three vertices, with polynomial $x^3-2x^2+x$.

Therefore \[ P_H(x)=(x^4-4x^3+6x^2-3x)-(x^3-2x^2+x) =x^4-5x^3+8x^2-4x. \]

Check: At $q=4$, the expression gives $256-320+128-16=48$. Independently, vertices $1$ and $3$ are adjacent, so they have $4\cdot3=12$ ordered color choices. Each of vertices $2$ and $4$ is adjacent to both $1$ and $3$, but they are not adjacent to each other; each therefore has $4-2=2$ choices, independently. The count is $12\cdot2\cdot2=48$.

How to Organize a Recurrence Tree

For a larger graph, it helps to record the recurrence before expanding every branch. Each node represents a graph and its polynomial; the two children for a chosen non-loop edge are the deletion graph and the contraction graph. The contraction child receives a minus sign. Continue until the leaves are edgeless or contain a loop, then work back up the tree.

Choose an edge.
Select a non-loop edge whose deletion and contraction are straightforward to describe. A symmetry or an edge whose contraction creates duplicate edges may keep the branches small.

Write both child graphs.
List the edges after deletion and contraction. In the contraction graph, merge the endpoints and suppress parallel edges; do not retain a loop as an ordinary constraint.

Continue to base cases.
Apply the same rule to each child that still has an edge. An edgeless graph on $n$ vertices contributes $x^n$; a graph with a loop contributes $0$.

Substitute and simplify.
At every node, subtract the contraction polynomial from the deletion polynomial. Combine like powers only after the two child expressions are identified.

Different edge choices can produce different recurrence trees, but the computed polynomial is the same because each application counts the same proper colorings. An efficient choice is one that keeps the smaller graphs recognizable and avoids creating many distinct branches. For a small graph, it is often useful to draw no picture at all: an explicit vertex and edge list makes the contraction checkable and prevents accidental changes to the graph.

Common Pitfalls and Checks

Reversing the subtraction. If a graph $G$ has a chosen edge $e$, the correct expression is $P_{G-e}-P_{G/e}$, not $P_{G/e}-P_{G-e}$. For the triangle, reversing the order would give $(x^2-x)-(x^3-2x^2+x)=-x^3+3x^2-2x$, which cannot count colorings: at $q=3$ it gives $-6$. The correction is to start with the deletion graph, which includes both endpoint-color cases, and subtract the equal-color case represented by contraction.

Keeping duplicate edges after contraction. In the chorded-square example, contraction creates two copies of each edge from the merged vertex to $2$ and $4$. These copies do not impose extra coloring restrictions. Replacing them by single edges gives the path on three vertices, not a graph with additional constraints.

Contracting the wrong pair. Contraction identifies the endpoints of the selected edge, not two vertices that merely look convenient. After merging them, check every original edge: an edge whose endpoints merge becomes a loop, while edges from the merged vertex to the same outside vertex become parallel edges. These details determine the correct child graph.

A useful final check is to evaluate the polynomial at a small positive integer and count colorings directly when feasible. This does not replace the recurrence proof, but it can expose an arithmetic or graph-reduction error. Also check that the final expression has no unexplained negative coloring count at the tested value; the triangle calculation shows how a sign error is immediately detectable.

Check Your Understanding

For each question, identify the graph reductions explicitly before simplifying.

For a single edge $G$, use deletion and contraction to derive $P_G(x)$.
Let $G$ have vertices $\{1,2,3,4\}$ and edges $\{12,23,34\}$. Choose edge $23$. Describe $G-e$ and $G/e$, then write the recurrence.
Why does contracting an edge in a simple graph sometimes produce parallel edges, and why may they be replaced by one edge when computing $P_G(x)$?
For the graph with $V=\{1,2,3\}$ and $E=\{12,23,13\}$, identify the graph obtained by deleting $12$ and the graph obtained by contracting $12$.
Explain why the recurrence tree must terminate, and state the polynomial assigned to an edgeless graph on $n$ vertices.