Loops, Parallel Edges, and Chromatic Polynomial Conventions

Why Conventions Matter

Deletion–contraction is a useful way to relate the chromatic polynomial of a graph to those of two smaller graphs. In a simple graph, contracting an edge can produce parallel edges: two distinct edges may then have the same pair of endpoints. To use the identity consistently, we need to decide how such edges—and loops—affect proper colorings. The answers are simple, but the loop convention is essential: a loop makes proper coloring impossible.

Unless stated otherwise, graphs are finite. In this tutorial we also allow multigraphs: distinct edges may have the same endpoints, and a loop is an edge whose two endpoints are the same vertex. A proper coloring with $q$ colors assigns one of the colors $1,\dots,q$ to each vertex so that the endpoints of every edge have different colors. The number $q$ is a positive integer when counting colorings.

Definition: For a graph $G$, its chromatic polynomial $P_G(q)$ is the polynomial whose value at each positive integer $q$ is the number of proper $q$-colorings of $G$. For graphs with loops or parallel edges, use these conventions: if $G$ has a loop, set $P_G(q)=0$; if $G$ has no loops, discard all but one edge from each set of parallel edges before taking the chromatic polynomial. The discarded edges do not change the proper-coloring condition.

These conventions agree with the coloring counts. A loop has both endpoints at one vertex, so its coloring condition would require that vertex's color to differ from itself. No coloring can satisfy this. Parallel edges with the same endpoints all require the same pair of vertices to receive different colors; satisfying that condition for one edge satisfies it for every edge in the set. The polynomial for a loopless multigraph is therefore the chromatic polynomial of its underlying simple graph.

Loops and Parallel Edges

Theorem: If $G$ has a loop, then $P_G(q)$ is the zero polynomial. If $G$ has no loops, replacing any nonempty set of parallel edges by a single edge preserves $P_G(q)$.

Proof. If $G$ has a loop at a vertex $v$, the edge condition requires the color of $v$ to differ from itself. This is impossible for every positive integer $q$, so the number of proper $q$-colorings is zero for every such $q$. By the convention defining $P_G$, the polynomial is zero. Now suppose $G$ has no loops, and let $G'$ be obtained by replacing a set of parallel edges between distinct vertices $u$ and $v$ by a single edge $uv$. A coloring is proper on the edges in that set exactly when the colors of $u$ and $v$ differ. That is precisely the condition imposed by the single edge $uv$. All other edge conditions are unchanged, so $G$ and $G'$ have the same proper $q$-colorings for every positive integer $q$, and hence the same chromatic polynomial. $\square$

Worked Example: A Loop Forces the Zero Polynomial

Let $G=(V,E)$ have $V=\{a,b,c\}$ and $E=\{aa,ab,bc\}$, where $aa$ is a loop at $a$. Determine $P_G(q)$.

For any positive integer $q$, a proper coloring would have to assign a color to $a$ different from itself because of the edge $aa$. If $a$ is assigned color $i$, the loop condition would require $i\ne i$, which is false. Thus there are no proper colorings, regardless of the colors assigned to $b$ and $c$.

Check: the number of proper colorings is $0$ for every positive integer $q$, so the polynomial under the stated convention is $P_G(q)=0$. In particular, substituting $q=2$ still gives $P_G(2)=0$; choosing colors for the other vertices cannot repair the loop condition.

Worked Example: Several Parallel Edges Give One Constraint

Let $G=(V,E)$ have $V=\{u,v,w\}$ and $E=\{uv,uv,uv,vw,vw,vw\}$. Thus there are three edges between $u$ and $v$, and three between $v$ and $w$. Count its proper colorings and find $P_G(q)$.

Choose a color for $u$: there are $q$ choices. Each of the three edges $uv$ imposes the same condition, so $v$ must differ in color from $u$, giving $q-1$ choices. Likewise, the three edges $vw$ impose one condition, so $w$ must differ from $v$, giving $q-1$ choices. There is no edge $uw$, so $w$ may have the same color as $u$. The count is therefore $$ P_G(q)=q(q-1)(q-1)=q(q-1)^2. $$

For a numerical check, substitute $q=3$: $P_G(3)=3(3-1)^2=3\cdot2^2=12$. Independently, replace each triple of parallel edges by one edge. The resulting graph has edges $uv$ and $vw$. Its colorings are counted by choosing $u$ in $3$ ways, then $v$ in $2$ ways, then $w$ in $2$ ways, giving $3\cdot2\cdot2=12$ as well.

Check: both the direct count with the parallel-edge conditions and the count on the simple graph give $12$ colorings with $3$ colors. The polynomial is unchanged by removing the repeated edges.

Contraction and the Deletion–Contraction Identity

For an edge $e=uv$, $G-e$ is the graph obtained by deleting that edge and keeping its vertices. If $e$ is not a loop, the contraction $G/e$ is formed by identifying $u$ and $v$ as one vertex and removing $e$. Every other edge remains, with its endpoints mapped to the identified vertices. This may create parallel edges; if an edge originally joined $u$ to $v$ other than $e$, it becomes a loop.

Theorem (Deletion–Contraction for a non-loop edge): Let $G$ be a finite graph that may have loops or parallel edges, and let $e$ be a non-loop edge. With loops assigned chromatic polynomial zero and parallel edges retained or simplified according to the conventions above, $$ P_G(q)=P_{G-e}(q)-P_{G/e}(q). $$

Proof. First fix a positive integer $q$. Consider the proper $q$-colorings of $G-e$. Divide them into two disjoint classes: those in which $u$ and $v$ have different colors, and those in which they have the same color. The first class consists exactly of the proper $q$-colorings of $G$, because adding $e=uv$ rules out precisely the colorings in which $u$ and $v$ agree.

The second class is in one-to-one correspondence with the proper $q$-colorings of $G/e$. To see this, take a coloring of $G-e$ with $u$ and $v$ assigned the same color, and give the identified vertex of $G/e$ that color. Every other vertex keeps its color. Each remaining edge of $G-e$ imposes exactly the condition of its corresponding edge after identification. If an edge becomes a loop in $G/e$, then it was an edge between $u$ and $v$ still present in $G-e$; it rules out equal colors at $u$ and $v$. Thus neither side of the correspondence has such a coloring. Conversely, a proper coloring of $G/e$ assigns a single color to the identified vertex, which gives equal colors to $u$ and $v$ and satisfies every edge condition of $G-e$. Therefore, for every positive integer $q$, the number of colorings of $G-e$ is the sum of the numbers of colorings of $G$ and $G/e$. Rearranging gives the displayed identity at every positive integer $q$. Both sides are polynomials, so they are equal as polynomials: a nonzero polynomial has only finitely many roots, whereas their difference vanishes at every positive integer. $\square$

The proof explains why the identity still works when contraction creates parallel edges. The coloring correspondence treats every resulting edge condition, but parallel edges between the same two vertices impose only one distinct-color requirement. It also explains what happens if contraction creates a loop: the contracted graph has no proper coloring, matching the fact that a coloring of $G-e$ cannot give $u$ and $v$ the same color when another edge still joins them.

Worked Example: Contraction Creates Parallel Edges

Let $G=(V,E)$ have $V=\{a,b,c,d\}$ and $E=\{ab,ac,bc,cd\}$. Apply deletion–contraction to $e=ab$, and verify the result by counting colorings.

For $G$, first color $a$ in $q$ ways. The edge $ab$ requires $b$ to have a different color, giving $q-1$ choices. The vertex $c$ must differ from both $a$ and $b$, because of $ac$ and $bc$, giving $q-2$ choices. Finally, $d$ must differ from $c$, giving $q-1$ choices. Therefore $$ P_G(q)=q(q-1)(q-2)(q-1)=q(q-1)^2(q-2). $$

After deleting $ab$, the edges are $ac,bc,cd$. Choose a color for $c$ in $q$ ways. Then $a$, $b$, and $d$ each have $q-1$ choices, since each must differ from $c$, and there are no edges between those three vertices. Hence $$ P_{G-e}(q)=q(q-1)^3. $$

After contracting $ab$, call the identified vertex $x$. The edges $ac$ and $bc$ both become edges between $x$ and $c$, so they are parallel. The remaining edge is $cd$. Choose a color for $x$ in $q$ ways, a different color for $c$ in $q-1$ ways, and a different color for $d$ in $q-1$ ways. Thus $$ P_{G/e}(q)=q(q-1)^2. $$

Subtracting gives $$ P_{G-e}(q)-P_{G/e}(q) =q(q-1)^3-q(q-1)^2 =q(q-1)^2\bigl((q-1)-1\bigr) =q(q-1)^2(q-2), $$ which agrees with the direct count for $G$.

Check: at $q=3$, the deletion count is $3(3-1)^3=3\cdot2^3=24$, and the contraction count is $3(3-1)^2=3\cdot2^2=12$. Their difference is $24-12=12$. Directly, the count for $G$ is $3(3-1)^2(3-2)=3\cdot2^2\cdot1=12$, as required.

Common Pitfalls and Practical Use

Do not count parallel edges as separate color restrictions. A common incorrect count for the second example is to choose $u$ in $q$ ways, $v$ in $q-3$ ways because there are three edges $uv$, and $w$ in $q-3$ ways because there are three edges $vw$. This treats each repeated edge as ruling out a new color. But every edge $uv$ forbids the same color: the color already assigned to $u$. The correct choices are $q$, then $q-1$, then $q-1$, giving $q(q-1)^2$. For instance, with $3$ colors the incorrect expression gives $3(3-3)^2=0$, while the direct choice count gives $3\cdot2\cdot2=12$.

Do not silently discard loops. Replacing parallel edges by one edge preserves the coloring condition, but deleting a loop would change the graph from one with no proper colorings to one that may have proper colorings. Under the convention here, loops must be retained when describing a contraction, and a contracted loop makes the contracted graph's polynomial zero.

Do not assume contraction stays simple. When two adjacent vertices are identified, edges from either of them to a common neighbor become parallel. They may be simplified after contraction because of the parallel-edge result, but they should not be mistaken for loops: a loop arises only from an edge whose endpoints are the two vertices being identified.

These conventions make deletion–contraction unambiguous. When applying it, choose a non-loop edge, form the deletion and contraction with their vertex and edge incidences specified, and then simplify parallel edges if convenient. If contraction creates a loop, the contracted term is zero; if it creates only parallel edges, those edges impose the same constraint as a single edge.

Check Your Understanding

For each question, state the coloring condition being used before giving a polynomial or conclusion.

Let $G$ have $V=\{x,y\}$ and $E=\{xx,xy\}$. What is $P_G(q)$, and which edge determines it?
A loopless graph has four edges joining $u$ to $v$. How many distinct color inequalities do those edges impose?
In a multigraph, a non-loop edge $e=uv$ is contracted while another edge between $u$ and $v$ remains. What does that remaining edge become, and what is the chromatic polynomial of the contracted graph?
Explain the two classes of colorings of $G-e$ used in the deletion–contraction proof.
Why can parallel edges created by contracting an edge be replaced by one edge without changing the chromatic polynomial?

Loops, Parallel Edges, and Chromatic Polynomial Conventions

What You'll Learn