Why Deleting and Contracting an Edge Give a Subtraction
A chromatic polynomial packages the number of proper colorings of a graph into a function of the number of available colors. The deletion-contraction identity gives a way to relate that polynomial to two smaller graphs. Its key idea is to begin with the graph after one edge has been removed: among its colorings, some assign different colors to the removed edge’s endpoints, while the rest assign them the same color.
All graphs in this tutorial are finite and simple. A proper coloring with \(q\) colors assigns one of \(q\) labeled colors to each vertex, with adjacent vertices receiving different colors. The chromatic polynomial \(P_G(q)\) is the polynomial whose value at each positive integer \(q\) counts the proper colorings of \(G\) with \(q\) colors. The existence of this polynomial is established in the earlier material on chromatic polynomials.
The contraction convention preserves exactly the coloring constraint we need. In a coloring of \(G/e\), the identified vertex has one color, and every neighbor of either \(u\) or \(v\) must have a different color from it. Repeated edges to the same neighbor do not impose an additional condition.
The Identity and Its Proof
Proof. Fix a positive integer \(q\). Consider all proper \(q\)-colorings of \(G-e\). Divide them into two disjoint classes: those in which \(u\) and \(v\) receive different colors, and those in which they receive the same color. A coloring in the first class satisfies the constraint on the deleted edge \(e\), so it is a proper coloring of \(G\). Conversely, every proper coloring of \(G\) is a proper coloring of \(G-e\) in which \(u\) and \(v\) have different colors. Thus the first class has size \(P_G(q)\).
For the second class, take a proper coloring of \(G-e\) in which \(u\) and \(v\) have the same color. Give the identified vertex of \(G/e\) that color, and keep the colors of every other vertex. Every edge of \(G/e\) comes from an edge of \(G-e\) incident with \(u\), with \(v\), or with neither. Its endpoints therefore have different colors. This gives a proper coloring of \(G/e\). Reversing the operation—giving both \(u\) and \(v\) the color of the identified vertex—recovers exactly one coloring in the second class. The two sets of colorings are in bijection, so the second class has size \(P_{G/e}(q)\). Consequently, \[ P_{G-e}(q)=P_G(q)+P_{G/e}(q) \] for every positive integer \(q\).
Rearranging gives the stated identity at every positive integer. Both sides are polynomials, so equality at all positive integers implies equality as polynomials: a nonzero polynomial cannot have infinitely many distinct roots. Therefore the identity holds as a polynomial identity. \(\square\)
The restriction that \(e\) is an edge of a simple graph ensures that it has two distinct endpoints. If the endpoints receive the same color after deletion, identifying them is precisely the operation that enforces that equality while retaining all the other coloring constraints.
Worked Applications
Worked Example: Deleting an Edge of a Triangle
Let \(G\) have vertex set \(\{1,2,3\}\) and edge set \(\{12,23,31\}\). Choose \(e=12\). Compute the two terms in the identity and check the result directly.
Deleting \(12\) leaves the path with edges \(23,31\). Choose a color for vertex \(1\): there are \(q\) choices. Vertex \(3\), adjacent to \(1\), then has \(q-1\) choices. Vertex \(2\), adjacent to \(3\), also has \(q-1\) choices. Therefore \[ P_{G-e}(q)=q(q-1)^2. \]
Contracting \(12\) identifies vertices \(1\) and \(2\). The resulting graph has two vertices, the identified vertex and vertex \(3\), joined by an edge. Its coloring count is \(q\) choices for the identified vertex and \(q-1\) for vertex \(3\), so \[ P_{G/e}(q)=q(q-1). \]
Subtracting gives \[ P_G(q)=q(q-1)^2-q(q-1)=q(q-1)(q-2). \] For a direct check, color vertex \(1\) in \(q\) ways; vertex \(2\), adjacent to \(1\), in \(q-1\) ways; and vertex \(3\), adjacent to both, in \(q-2\) ways. This gives the same polynomial.
Check at \(q=3\): deletion gives \(3(3-1)^2=3\cdot4=12\) colorings; contraction gives \(3(3-1)=3\cdot2=6\). Their difference is \(12-6=6\). Directly, the triangle has \(3\cdot2\cdot1=6\) proper colorings.
Worked Example: A Diamond Graph
Let \(G\) have vertex set \(\{a,b,c,d\}\) and edge set \(\{ab,ac,bc,ad,bd\}\). Choose \(e=ab\). Here the deletion graph is a 4-cycle, and contraction produces a path with two edges.
In \(G-e\), the edges are \(ac,cb,bd,da\). Count its colorings by first choosing colors for \(a,c,d\). There are \(q\) choices for \(a\), and \(q-1\) choices for \(c\), since \(ac\) is an edge. The vertex \(d\) must differ from \(a\). Separate two cases:
- If \(c\) and \(d\) have the same color, there are \(q-1\) choices for their common color. Vertex \(b\) must differ from that color, giving \(q-1\) choices. This case contributes \(q(q-1)(q-1)=q(q-1)^2\).
- If \(c\) and \(d\) have different colors, there are \(q-2\) choices for \(d\), since it must differ from both \(a\) and \(c\). Vertex \(b\) must differ from both \(c\) and \(d\), giving \(q-2\) choices. This case contributes \(q(q-1)(q-2)^2\).
Thus \[ P_{G-e}(q)=q(q-1)^2+q(q-1)(q-2)^2. \] After contracting \(ab\), the identified vertex is adjacent to \(c\) and \(d\), and there is no edge \(cd\). This is a three-vertex path with the identified vertex in the middle. Choose its color in \(q\) ways, then choose each endpoint’s color in \(q-1\) ways. Hence \(P_{G/e}(q)=q(q-1)^2\). Subtracting, \[ P_G(q)=q(q-1)(q-2)^2. \]
Check at \(q=3\): deletion gives \(3(2)^2+3(2)(1)^2=12+6=18\); contraction gives \(3(2)^2=12\); the difference is \(18-12=6\). Directly, choose a color for \(a\) in \(3\) ways and a different color for \(b\) in \(2\) ways. Each of \(c,d\) is adjacent to both \(a,b\), so each has \(3-2=1\) choice; there is no edge \(cd\). The direct count is \(3\cdot2\cdot1\cdot1=6\), as required.
Worked Example: Contraction with Repeated Adjacencies
Let \(G=K_4\), with vertex set \(\{a,b,c,d\}\) and edge set \(\{ab,ac,ad,bc,bd,cd\}\). Choose \(e=ab\). Both \(a\) and \(b\) are adjacent to \(c\) and to \(d\), so contraction creates repeated adjacencies unless they are represented by single edges.
In \(G-e\), the edges are \(ac,ad,bc,bd,cd\). Choose a color for \(a\) in \(q\) ways, for \(c\) in \(q-1\) ways, and for \(d\) in \(q-2\) ways because \(d\) must differ from both \(a\) and \(c\). Vertex \(b\) must differ from \(c\) and \(d\); there are \(q-2\) choices. It need not differ from \(a\), because \(ab\) was deleted. Therefore \[ P_{G-e}(q)=q(q-1)(q-2)^2. \]
After contracting \(ab\), the identified vertex is adjacent to \(c\) and \(d\), and \(cd\) remains an edge. The repeated adjacencies to \(c\) and \(d\) impose no extra coloring conditions. The result is \(K_3\), so its colorings are counted by choosing three distinct colors in order: \[ P_{G/e}(q)=q(q-1)(q-2). \] The identity gives \[ P_G(q)=q(q-1)(q-2)^2-q(q-1)(q-2) =q(q-1)(q-2)(q-3). \]
Check at \(q=4\): deletion gives \(4\cdot3\cdot2^2=48\); contraction gives \(4\cdot3\cdot2=24\); the difference is \(48-24=24\). Directly, the four vertices of \(K_4\) must receive four distinct colors, giving \(4\cdot3\cdot2\cdot1=24\). This also confirms why suppressing repeated adjacencies after contraction is appropriate: duplicate edges do not require a vertex to avoid a color more than once.
How to Use the Identity Correctly
The theorem applies to any chosen edge \(e\) of a finite simple graph. It does not require the graph to be connected, and it does not require the edge to have any special position. The graph \(G-e\) retains every vertex; \(G/e\) has one fewer vertex because the two distinct endpoints are identified.
The subtraction has a specific meaning. The colorings of \(G-e\) include both the colorings that already satisfy the deleted edge and those that fail precisely that constraint. The first group counts \(P_G(q)\). The second group counts \(P_{G/e}(q)\). Therefore it is the contraction term that must be subtracted. The examples show that this grouping works even when contraction merges repeated adjacencies.
Common mistake: adding the contraction term. For the triangle in the first example, adding would give \[ P_{G-e}(q)+P_{G/e}(q)=q(q-1)^2+q(q-1). \] At \(q=3\), this is \(12+6=18\), but the triangle has only \(3\cdot2\cdot1=6\) proper colorings. The error is that the contracted graph counts the colorings of \(G-e\) in which the endpoints of the deleted edge receive the same color. These are precisely the colorings to exclude, so the correct calculation is \(12-6=6\).
Another useful check is to track which graph each count describes before doing algebra: the deletion term allows the endpoints to match, while the contraction term counts exactly that matching-color case. If those roles are reversed, or if the contraction term is added, the partition of colorings has been misread.
Check Your Understanding
For each question, identify the deletion and contraction graphs before applying the identity.
- Let \(G\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34,41,13\}\). Choose \(e=13\). Describe \(G-e\) and \(G/e\), including any repeated adjacencies that contraction creates.
- In the proof, why do colorings of \(G-e\) in which \(u\) and \(v\) have different colors count \(P_G(q)\)?
- For the graph on \(\{a,b,c,d\}\) with edges \(\{ab,ac,bc,ad,bd\}\), verify the deletion-contraction identity at \(q=4\).
- Explain why equality of the two coloring counts for every positive integer \(q\) gives equality of the chromatic polynomials.
- State which term must be subtracted in the identity and explain what set of colorings that term counts.