Motivation
A proper coloring answers whether adjacent vertices can be given different colors. Counting all such assignments asks a richer question: how does the number change with the size of the named palette? Surprisingly, one polynomial describes the answer for every nonnegative integer palette size.
The polynomial can be constructed by forbidding monochromatic edges or by splitting according to whether the endpoints of one deleted edge receive the same color. These methods lead to different proofs of the same object. They also expose useful limitations: counting labeled colors is not counting unnamed color classes, and equal chromatic polynomials do not force two graphs to be isomorphic.
Definitions
Definition 10.1.1
(Proper colorings and the named palette)
Let be a finite simple undirected graph with vertices and edges. For an integer , a proper -coloring is a function assigning different values to adjacent vertices. It need not use every available color. Distinct palette names give distinct assignments. Write for the number of proper colorings.
A graph with no vertices has one coloring, the empty function, even when the palette is empty. A nonempty graph has no coloring with an empty palette. The chromatic number of a nonempty graph is the least positive integer admitting a proper coloring; for the zero-vertex graph we use zero.
For , let be the number of connected components in the spanning graph , including isolated vertices. For an edge , the deletion removes that edge. The contraction identifies its endpoints, removes the contracted edge and consolidates repeated edges into single edges. Because the original graph is simple, no other loop arises. The resulting simple graph represents equality of the two endpoint colors.
Theorem/Proposition
Theorem 10.1.2
(Existence and first coefficients of the chromatic polynomial)
The coloring count agrees, at every nonnegative integer , with the integer-coefficient polynomial
It is monic of degree . For its constant term is zero and its coefficient of is . For , the coefficient of is , where is the number of triangles. The zero-vertex polynomial is one.
Theorem 10.1.3
(Deletion–contraction and product rules)
For every edge ,
A disjoint union satisfies . If is the union of two graphs whose vertex intersection is exactly one vertex and which have no further joining edges, then
This is a polynomial identity, so it is meaningful at zero without dividing numerically by zero.
Theorem 10.1.4
(Trees, forests and cycles)
A tree on vertices has polynomial . A forest with vertices and components has polynomial . A cycle with has
Proof sketch or proof idea
Proof
(Inclusion–exclusion and the first coefficients)
Begin with all colorings and let each forbidden event require the endpoints of one edge to have equal color. Requiring all events indexed by forces every component of to be monochromatic. The components choose colors independently, giving assignments. Inclusion–exclusion proves the sum. For the zero-vertex graph the term is the constant polynomial , including at zero.
Only the empty edge subset has components, proving monicity. A nonempty graph has at least one component in every spanning subgraph, so there is no constant term. To get components, a simple graph must contribute exactly one selected edge, giving coefficient . To get components, every two-edge subset contributes positively. The only additional possibility is three edges forming a triangle, contributing negatively. Indeed, total component reduction two permits either two separate two-vertex components or one three-vertex component; a simple three-vertex graph has at most three edges. This proves the triangle coefficient formula.
Proof
(Deletion–contraction by endpoint colors)
For deletion–contraction, partition proper colorings of into those with different endpoint colors and those with equal endpoint colors. The first group is exactly the proper colorings of . Identifying equal-colored endpoints gives a bijection from the second group to proper colorings of . Multiple adjacency constraints created by identification are identical, which is why consolidating parallel edges is harmless. Equality holds at every integer palette size and therefore as a polynomial identity.
Proof X-ray
What the single case split in deletion–contraction uses
The proof starts from , not from : deleting removes one constraint, so the colorings of include all colorings of . The one case split is by whether and receive the same color. The unequal case reinstates exactly the deleted constraint and changes nothing else, so it counts . The equal case is where contraction enters. Merging into one vertex is reversible because the two endpoint colors coincide, and must differ from every neighbor of or of . When and share a neighbor , the two resulting constraints between and are one and the same, which is why consolidating parallel edges loses nothing. Simplicity of is used at this point: the only loop identification could create comes from itself, which is removed. The argument proves the identity at each integer ; it becomes a polynomial identity because two polynomials that agree at infinitely many points are equal.
Proof
(Products over disjoint and one-vertex unions)
Disjoint graphs choose their colorings independently from the same palette, proving the product rule. For a one-vertex union and positive integer , symmetry of color names gives exactly colorings of each piece with the shared vertex assigned a specified color. Choose that color in ways and combine the two pieces, proving . Equality for infinitely many positive integers proves the polynomial identity. Each piece has a vertex, so its polynomial has a factor ; the formal quotient by one factor is a polynomial, not an undefined evaluation at zero.
Proof
(Trees, forests and cycles)
Root a tree. Its root has choices; every other vertex has choices after its parent is colored, with no additional edge constraint. This proves the tree formula, and multiplying over components gives the forest formula, including the empty forest. The triangle has polynomial , agreeing with the cycle formula at three. For , deleting a cycle edge leaves a path on vertices and contracting it gives . Substituting the inductive cycle expression into deletion–contraction gives the displayed formula. The triangle is the separate base case because contracting its edge gives one simple edge, not a simple two-cycle.
Worked examples
Worked example 10.1.5
(A four-cycle by deletion and contraction)
Delete one edge of to obtain a four-vertex path and contract it to obtain a triangle. Hence
At two colors this is two assignments, and at three colors it is eighteen. The coefficients record four edges and triangles, consistent with the graph.
Worked example 10.1.6
(A triangle with a leaf shares one vertex between pieces)
Attach a leaf to a triangle vertex. Combining the triangle polynomial with an edge polynomial and dividing formally by the shared-vertex factor gives . At three colors there are twelve colorings. Equivalently, color the triangle in six ways and choose either of the two colors different from the neighbor for the leaf. Both computations count named palette assignments.
Worked example 10.1.7
(The polynomial is not a complete graph invariant)
The path on four vertices and the star with three leaves are nonisomorphic: their degree lists are and . Both are trees and therefore have polynomial . Their coloring counts agree for every palette size, while their adjacency structures differ. A count polynomial can preserve useful statistics without encoding the entire graph.
Why the spanning vertex set must be retained
In the inclusion–exclusion formula, deleting edges does not delete their endpoints. Isolated vertices still choose colors independently and contribute components. In particular, the empty edge subset has exactly as many components as the original vertex count. Counting only components containing an edge would erase those free color choices and destroy even the polynomial's leading term.
The forbidden events are not disjoint. A monochromatic triangle satisfies three edge-equality events, while only two of its equalities are independent constraints. Inclusion–exclusion keeps the triple intersection and corrects that overlap. This explains the triangle correction in the third coefficient: the formula counts constraints by their connected effect, not just by the number of selected edges.
Graph simplicity is important for the coefficient interpretation. Parallel edges impose the same color inequality, so counting them as different graph edges would not produce coefficient minus their total multiplicity. Loops would forbid every coloring. The stated domain excludes both phenomena, while contraction explicitly returns to the simple setting.
Named colors and unnamed independent classes
A proper coloring partitions the vertices into its nonempty color classes, each of which is independent. If a partition has exactly blocks, assigning distinct palette names to them gives colorings. Therefore another expansion is
where counts partitions of the vertex set into nonempty independent blocks. This follows by a reversible fiber decomposition, not by dividing the entire coloring count by a fixed factorial.
For an edgeless graph, every block is independent, so these coefficients are the second-kind Stirling numbers. The identity becomes the expansion of in falling factorials. For a graph with edges, forbidden co-membership changes the block-partition counts. The relationship connects graph coloring to labeled-set enumeration while retaining the different object definitions.
Counterexample mode
Dividing by the palette factorial is not generally valid
Two isolated vertices have nine colorings from a three-color palette. Dividing by gives one and a half, which cannot count unnamed partitions. There are actually two color-class partitions: one block containing both vertices, or two singleton blocks. They have three and six named realizations respectively. Unused colors make the fiber sizes depend on the number of nonempty classes.
Counting, decision and computational cost
For a nonempty graph, the smallest positive integer where the polynomial is positive is its chromatic number. The equality follows from the counting interpretation at integer arguments. Values at arbitrary real or negative arguments are polynomial evaluations, not counts of palettes with a noninteger or negative number of colors.
Deletion–contraction terminates because each branch removes an original edge, either by deletion or contraction, with parallel consolidation possibly removing more. A straightforward recursive calculation can still have exponentially many branches. The existence of a polynomial in the palette variable does not mean that its coefficients can be computed in polynomial time in the graph size by this method.
Special structure can simplify the calculation. Forests have a direct product formula; a cut vertex separates independent pieces once its color is fixed. These simplifications must be justified by actual decomposition hypotheses. Multiplying arbitrary subgraph polynomials would overcount or ignore constraints across their intersection.
Concept lensCombinatorial
One graph has several distinct counting descriptions
Inclusion–exclusion counts components forced monochromatic by selected equalities. Deletion–contraction separates unequal and equal endpoint cases. The falling-factorial expansion counts independent vertex partitions before naming their classes. Each describes the same colorings but organizes different intermediate objects, making different identities transparent.
Common mistakes
Common mistake
(A palette size is not the number of colors used)
A proper coloring need not use all palette names. For a single edge, , and none of these six colorings uses all three colors. Reading as the number of colorings with exactly colors would give zero here. The number of colorings that use all palette colors is , with from the falling-factorial expansion above; it is not .
Common mistake
(Deletion–contraction is not automatically efficient)
A maximal chain of smaller graph calculations is not automatically an efficient algorithm; recursion size and arithmetic must be analyzed separately. For a forest with edges, contraction never creates parallel edges, so both branches keep edges and stay forests; recursing until no edge remains produces exactly edgeless leaves, although the product formula gives the answer at once.
A contraction merges endpoint colors, whereas deleting a vertex would remove a color choice altogether.
The first coefficients reveal vertices, edges and triangles, but the tree example proves they do not determine isomorphism. Also do not apply the cycle-contraction recurrence at a fictional simple two-cycle; the three-cycle base must be checked directly.
Summary
Proper named-palette colorings define an integer polynomial through inclusion–exclusion. Deletion–contraction and graph decompositions provide complementary computations. Tree and cycle formulas, coefficient statistics and independent-class expansions show both the polynomial's structural information and its limits.
Exercises
Quick check
(Find the polynomial of a forest with seven vertices and three components. How many proper two-colorings and three-colorings does it have?)
Include isolated components if present.
Solution · Answer
The polynomial is . At two colors the value is eight; at three it is . Isolated vertices are components with one root choice and no extra factor, so the formula already includes them.
Quick check
(A simple five-vertex graph has leading terms . Determine its edge and triangle counts.)
The problem gives a possible coefficient pattern; the two statistics have different formulas.
Solution · Answer
The coefficient of is minus the edge count, so . The coefficient of equals , hence . The pattern is realizable, for example by removing an edge from a four-clique and attaching one new leaf: this has six edges and two triangles. No claim about a unique graph follows.
Quick check
(Compute the polynomial of the complete graph on four vertices and verify the edge/triangle coefficient interpretation.)
Choose colors for successive mutually adjacent vertices.
Solution · Answer
The polynomial is . It records six edges, and its third coefficient gives triangles, exactly the four three-vertex subsets. For palette sizes below four the product vanishes, as required; at four there are assignments.