Chromatic Polynomials of Trees and Forests

Coloring a Tree One Vertex at a Time

In a tree, the absence of cycles gives a useful way to count proper colorings: remove a leaf, count the colorings of the smaller tree, and then restore the leaf. A restored leaf has exactly one neighbor, so its color has a simple number of choices. Repeating this argument gives a formula depending only on the number of vertices. For a forest, the components can be colored independently, giving a closely related formula.

All graphs in this tutorial are finite and simple. A proper coloring with $q$ colors assigns one of $q$ labeled colors to each vertex so that adjacent vertices receive different colors. The chromatic polynomial $P_G(q)$ is the polynomial whose value at each positive integer $q$ counts the proper colorings of $G$. The existence of this polynomial is established in the earlier material on chromatic polynomials. It is distinct from the chromatic number $\chi(G)$, which is the least number of colors needed for a proper coloring.

Definition: A tree is a connected graph with no cycles. A forest is a graph with no cycles; it may be disconnected or have isolated vertices. A connected component is a maximal connected subgraph. Write $n=|V(G)|$ for the number of vertices and $c$ for the number of components of a forest.

When a coloring count is expressed as a polynomial, it is enough to show that the formula gives the correct count for every positive integer $q$. Two polynomials that agree at every positive integer are equal: a nonzero polynomial has only finitely many roots. We will use this standard polynomial identity fact to pass from coloring counts to polynomial formulas.

Why a Tree Has a Leaf

Lemma: Every tree with at least two vertices has a vertex of degree $1$, called a leaf.

Proof. Let $T$ be a tree with at least two vertices. Since $T$ is finite and connected, it has a path with the greatest possible length. Let $v$ be one endpoint of that path. The endpoint has at least one neighbor, namely the next vertex on the path. If $v$ had a neighbor outside the path, that neighbor could be added to make a longer path, contradicting the choice of the path. If $v$ had another neighbor on the path besides its next vertex, the segment of the path between those two neighbors together with the two edges to $v$ would form a cycle, contradicting that $T$ has no cycles. Thus $v$ has exactly one neighbor, so it is a leaf. $\square$

If $v$ is a leaf of a tree $T$, then $T-v$, the graph obtained by deleting $v$ and its incident edge, is a tree when it has at least one vertex. It has no cycles because it is a subgraph of an acyclic graph. It is connected because a path between two remaining vertices cannot use $v$ as an internal vertex: an internal vertex of a path has at least two incident path edges, whereas $v$ has degree $1$. Thus deleting a leaf leaves a smaller tree to which the same counting argument applies.

The Chromatic Polynomial of a Tree

Theorem: If $T$ is a tree on $n\geq 1$ vertices, then $$ P_T(q)=q(q-1)^{n-1}. $$

Proof. We use induction on $n$. If $n=1$, the single vertex can receive any of the $q$ colors, so $P_T(q)=q=q(q-1)^0$.

Now let $n\geq 2$, and assume the formula holds for every tree on $n-1$ vertices. By the lemma, $T$ has a leaf $v$; let $u$ be its unique neighbor. Deleting $v$ gives a tree $T-v$ on $n-1$ vertices. For any proper coloring of $T-v$, the color of $u$ is already fixed. When $v$ is restored, it may receive any of the $q$ colors except the color of $u$, so there are exactly $q-1$ extensions of that coloring. Therefore, for every positive integer $q$, $$ P_T(q)=(q-1)P_{T-v}(q). $$ By the induction hypothesis, $P_{T-v}(q)=q(q-1)^{n-2}$. Substitution gives $$ P_T(q)=(q-1)q(q-1)^{n-2}=q(q-1)^{n-1}. $$ This holds for every positive integer $q$, so the polynomial identity fact gives the claimed formula. $\square$

The count has a direct interpretation: choose a color for one vertex in $q$ ways, then add vertices in an order that starts at that vertex and always adds a vertex next to one already added. Each added vertex has at least one earlier neighbor, so it cannot use that neighbor’s color. The leaf-removal proof establishes the exact count without requiring a particular ordering.

Worked Example: The Path on Five Vertices

Let $T$ have vertex set $V(T)=\{1,2,3,4,5\}$ and edge set $E(T)=\{12,23,34,45\}$. This is a tree with $n=5$, so the formula gives $$ P_T(q)=q(q-1)^{5-1}=q(q-1)^4. $$

For a direct count with $q=3$, choose a color for vertex $1$ in $3$ ways. Vertex $2$ has $2$ choices because it is adjacent to $1$; vertex $3$ has $2$ choices because it is adjacent to $2$; vertex $4$ has $2$ choices because it is adjacent to $3$; and vertex $5$ has $2$ choices because it is adjacent to $4$. The count is $3\cdot2\cdot2\cdot2\cdot2=3\cdot16=48$.

Check: substituting $q=3$ into the polynomial gives $3(3-1)^4=3\cdot2^4=3\cdot16=48$, agreeing with the direct count.

Worked Example: A Branched Tree

Let $T$ have vertex set $V(T)=\{1,2,3,4,5,6\}$ and edge set $E(T)=\{12,13,14,45,46\}$. The graph is connected and has no cycles: vertices $2,3,5,6$ are leaves, and the only remaining edges join these leaves to $1$ or $4$. It is a tree on $6$ vertices, so $$ P_T(q)=q(q-1)^{6-1}=q(q-1)^5. $$

For a direct count with $q=4$, choose a color for vertex $1$ in $4$ ways. Each of vertices $2,3,4$ has $3$ choices after the color of $1$ is fixed: vertices $2$ and $3$ are adjacent to $1$, and vertex $4$ is also adjacent to $1$. Once vertex $4$ is colored, vertices $5$ and $6$ each have $3$ choices, since each is adjacent only to $4$. The total is $4\cdot3\cdot3\cdot3\cdot3\cdot3=4\cdot3^5=4\cdot243=972$.

Check: the formula gives $4(4-1)^5=4\cdot3^5=4\cdot243=972$. This agrees with the choices counted directly from the specified edges.

Extending the Formula to Forests

Theorem: If a forest $F$ has $n$ vertices and $c$ components, then $$ P_F(q)=q^c(q-1)^{n-c}. $$ For the empty graph, take $n=c=0$; the formula gives $P_F(q)=1$.

Proof. First suppose $F$ is nonempty, and write its components as $T_1,\dots,T_c$, with $n_i$ vertices in $T_i$. Each component is a tree: it is connected by the definition of component and has no cycles because $F$ has none. A proper coloring of $F$ is exactly a choice of a proper coloring for each component. Components have no edges between them, so colors may be reused in different components, and the choices multiply. The tree formula therefore gives $$ P_F(q)=\prod_{i=1}^{c}P_{T_i}(q) =\prod_{i=1}^{c}q(q-1)^{n_i-1} =q^c(q-1)^{\sum_{i=1}^{c}(n_i-1)}. $$ Since the components partition the vertex set, $\sum_{i=1}^{c}n_i=n$, and hence $\sum_{i=1}^{c}(n_i-1)=n-c$. Thus $P_F(q)=q^c(q-1)^{n-c}$. The equality holds for every positive integer $q$, so it holds as a polynomial identity. If $F$ is empty, it has one coloring—the empty assignment—for every positive integer $q$, so $P_F(q)=1$. With $n=c=0$, the displayed formula is $q^0(q-1)^0=1$, as required. $\square$

An isolated vertex is a component with one vertex. Its contribution is $q(q-1)^0=q$, since it can receive any color. It must therefore be included in the component count $c$, even though it has no incident edges.

Worked Example: A Forest with an Isolated Vertex

Let $F$ have vertex set $V(F)=\{1,2,3,4,5,6\}$ and edge set $E(F)=\{12,23,45\}$. Its components have vertex sets $\{1,2,3\}$, $\{4,5\}$, and $\{6\}$. Thus $n=6$ and $c=3$, and the forest formula gives $$ P_F(q)=q^3(q-1)^{6-3}=q^3(q-1)^3. $$

For a direct count with $q=3$, the component on $\{1,2,3\}$ is a path: vertex $1$ has $3$ choices, vertex $2$ then has $2$, and vertex $3$ has $2$ because it is adjacent to $2$. It has $3\cdot2\cdot2=12$ colorings. The edge $45$ has $3\cdot2=6$ colorings, and the isolated vertex $6$ has $3$ choices. Because there are no edges between these components, the total is $12\cdot6\cdot3=216$.

Check: substituting $q=3$ into the forest formula gives $3^3(3-1)^3=27\cdot8=216$, agreeing with the component-by-component count.

Common Pitfall: Counting the Root Twice

A frequent error is to assign $q-1$ choices to every vertex of a tree, including its first vertex. The first vertex has no previously colored neighbor constraining its color, so it has $q$ choices, not $q-1$.

For a concrete example, let $S$ have vertex set $V(S)=\{1,2,3,4\}$ and edge set $E(S)=\{12,13,14\}$. This is a tree with $4$ vertices. The incorrect calculation $q(q-1)^4$ would give $3\cdot2^4=3\cdot16=48$ colorings when $q=3$. The correct calculation chooses the color of vertex $1$ in $3$ ways and then chooses each of the three leaves’ colors in $2$ ways, giving $3\cdot2^3=3\cdot8=24$. The tree formula agrees: $P_S(q)=q(q-1)^{4-1}=q(q-1)^3$, and $P_S(3)=3\cdot2^3=24$.

The forest formula also requires care with components. Using $q(q-1)^{n-1}$ for a disconnected forest treats it as though it had just one component. Instead, each component contributes its own initial factor $q$; the exponent $n-c$ counts the remaining vertices, one fewer than the number in each component.

The formulas rely on the graph being acyclic. In a graph with a cycle, deleting a vertex can leave additional constraints among the remaining vertices, so the leaf argument does not apply as stated. Before using either formula, check that the graph is a tree or a forest, and count its components as well as its vertices.

Check Your Understanding

Use the tree and forest formulas, and check your reasoning against the edges and components in each question.

For the tree with vertex set $\{1,2,3,4\}$ and edge set $\{12,23,34\}$, find its chromatic polynomial and its number of proper colorings with $4$ colors.
A forest has $9$ vertices and $3$ components. Find its chromatic polynomial.
Explain why an isolated vertex contributes a factor of $q$ to the chromatic polynomial of a forest.
For a tree with one vertex, verify the tree formula directly, including the exponent of $q-1$.
What is the chromatic polynomial of the empty graph under the forest formula, and how many components does it have?