The Highest-Degree Coefficients

What the Highest-Degree Terms Record

The chromatic polynomial $P_G(q)$ counts proper vertex colorings of a graph $G$ when the number $q$ of available colors is a positive integer. Its highest-degree coefficients have a simple interpretation: the coefficient of $q^{n-1}$ records the edges, while the coefficient of $q^{n-2}$ records pairs of edges with a correction for triangles. Here all graphs are finite and simple, so they have no loops or multiple edges.

Write $n=|V(G)|$ for the order of $G$ and $m=|E(G)|$ for its size. A triangle is a cycle of length $3$; write $t$ for the number of triangles in $G$. We will derive the coefficients using inclusion–exclusion over the events that an edge has endpoints of the same color.

Definition: A proper coloring with $q$ colors assigns one of $q$ 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$ is the number of proper colorings. The graph with no vertices has one coloring, the empty assignment, so its chromatic polynomial is $1$.

An Inclusion–Exclusion Formula

For a subset $A\subseteq E(G)$, consider the spanning subgraph with vertex set $V(G)$ and edge set $A$. Let $k(A)$ be its number of connected components, counting isolated vertices. The number $k(A)$ tells us how many color choices remain if the endpoints of every edge in $A$ are required to have the same color.

Proposition: For every finite simple graph $G$, $$ P_G(q)=\sum_{A\subseteq E(G)}(-1)^{|A|}q^{k(A)}. $$

Proof. Fix a positive integer $q$, and consider all $q^{n}$ assignments of colors to the vertices, including assignments that are not proper. For each edge $e$, let $B_e$ be the event that the endpoints of $e$ have the same color. A coloring is proper exactly when it belongs to none of the events $B_e$. Inclusion–exclusion therefore counts proper colorings by summing, over all $A\subseteq E(G)$, $(-1)^{|A|}$ times the number of assignments belonging to every $B_e$ for $e\in A$.

Belonging to all those events means that the color must be constant on every connected component of the spanning subgraph with edge set $A$. Each of its $k(A)$ components can be assigned any of the $q$ colors, independently, so there are $q^{k(A)}$ such assignments. This proves the displayed equality for every positive integer $q$. Both sides are polynomials in $q$, and polynomials that agree at infinitely many values are identical; hence the equality holds as a polynomial identity. $\square$

The First Three Degree Positions

Theorem: If $G$ is a finite simple graph of order $n\ge 2$, with $m$ edges and $t$ triangles, then the coefficients of $q^n$, $q^{n-1}$, and $q^{n-2}$ in its chromatic polynomial are respectively $$ 1,\qquad -m,\qquad \binom{m}{2}-t. $$ Thus the terms in those degree positions are $q^n-mq^{n-1}+\bigl(\binom{m}{2}-t\bigr)q^{n-2}$. A coefficient may be zero, and terms of lower degree are not specified by this formula.

Proof. In the inclusion–exclusion formula, the term associated with $A\subseteq E(G)$ has degree $k(A)$, and its sign is $(-1)^{|A|}$. The empty edge set has $k(\varnothing)=n$ and contributes $q^n$ with coefficient $1$. Every nonempty $A$ has at least one edge, so at least two vertices lie in the same component and $k(A)\le n-1$. Thus no other subset contributes to $q^n$.

A term contributes to $q^{n-1}$ exactly when $k(A)=n-1$. Adding an edge to the spanning graph decreases the number of components by at most one. Consequently, a nonempty edge set has $n-1$ components only if it consists of one edge: one component then contains its two endpoints, and the remaining $n-2$ vertices are isolated. Conversely, every single-edge set has $n-1$ components. There are $m$ such sets, each with sign $-1$, so the coefficient of $q^{n-1}$ is $-m$.

For the coefficient of $q^{n-2}$, we need the subsets $A$ with $k(A)=n-2$. Each connected component on $s$ vertices contributes $s-1$ to the decrease in component count, since it replaces $s$ isolated vertices by one component. Thus the total decrease $n-k(A)$ is $2$. The non-isolated components must therefore have either one component on three vertices or two components on two vertices each.

Every two-edge subset of $E(G)$ has exactly this total decrease: if its edges share an endpoint, they form a connected component on three vertices; if not, they form two separate components on two vertices. These subsets contribute $+1$ each, because their size is two, giving $\binom{m}{2}$ in total.

It remains to consider edge subsets of other sizes with $k(A)=n-2$. In the case of two components on two vertices, simplicity allows only one edge in each component, so there are exactly two edges. In the case of one component on three vertices, simplicity allows at most three edges. A three-edge subset has the required component count precisely when its three edges form a triangle: on three vertices, three distinct edges give all three possible pairs and form a connected component. Each triangle contributes one three-edge subset with sign $-1$. There are $t$ such subsets, so their total contribution is $-t$. No larger subset can have $k(A)=n-2$. Adding the contributions gives $\binom{m}{2}-t$, as claimed. $\square$

The restriction $n\ge2$ ensures that all three degree positions in the formula are nonnegative powers. For a graph on one vertex, $P_G(q)=q$; for a graph on no vertices, $P_G(q)=1$. The formula does not describe a $q^{n-2}$ term in those cases.

Worked Applications

Worked Example: A Path on Four Vertices

Let $G$ have $V(G)=\{1,2,3,4\}$ and $E(G)=\{12,23,34\}$. It has $n=4$ vertices and $m=3$ edges. It has no triangles, so $t=0$. The theorem gives the coefficient of $q^2$ as $\binom{3}{2}-0=3-0=3$, and the first three degree positions are $$ q^4-3q^3+3q^2. $$

We can check by counting colorings directly. Vertex $1$ has $q$ choices. Each of $2,3,4$, in that order, has $q-1$ choices because it must differ from its preceding neighbor. Hence $P_G(q)=q(q-1)^3$. Expanding, $(q-1)^3=q^3-3q^2+3q-1$, so $P_G(q)=q^4-3q^3+3q^2-q$. Its three highest-degree coefficients agree with the theorem.

Worked Example: A Triangle with a Pendant Vertex

Let $G$ have $V(G)=\{a,b,c,d\}$ and $E(G)=\{ab,bc,ca,cd\}$. The edge count is $m=4$, and the only triangle is $abc$, so $t=1$. The coefficient of $q^2$ is $\binom{4}{2}-1=6-1=5$. The predicted highest-degree terms are $q^4-4q^3+5q^2$.

For a direct check, color $a,b,c$ first. Their triangle has $q$ choices for $a$, $q-1$ choices for $b$, and $q-2$ choices for $c$. Since $d$ is adjacent only to $c$, it has $q-1$ choices. Therefore $P_G(q)=q(q-1)(q-2)(q-1)=q(q-1)^2(q-2)$. Multiplying, $(q-1)^2(q-2)=(q^2-2q+1)(q-2)=q^3-4q^2+5q-2$. Thus $P_G(q)=q^4-4q^3+5q^2-2q$, which verifies the predicted coefficients.

Worked Example: Two Triangles Sharing an Edge

Let $G$ have $V(G)=\{1,2,3,4\}$ and $E(G)=\{12,13,14,23,24\}$. The graph has $n=4$ vertices and $m=5$ edges. Its triangles are $123$ and $124$; the triples $134$ and $234$ are not triangles because $34\notin E(G)$. Thus $t=2$, and the coefficient of $q^2$ is $\binom{5}{2}-2=10-2=8$. The predicted terms are $q^4-5q^3+8q^2$.

For an independent check, choose colors for vertices $1$ and $2$, which are adjacent: there are $q$ choices for $1$ and $q-1$ for $2$. Each of vertices $3$ and $4$ is adjacent to both $1$ and $2$, so each has $q-2$ choices. There is no edge $34$, so these choices do not constrain one another. Hence $P_G(q)=q(q-1)(q-2)^2$. Since $(q-2)^2=q^2-4q+4$, we obtain $(q-1)(q^2-4q+4)=q^3-5q^2+8q-4$, and therefore $P_G(q)=q^4-5q^3+8q^2-4q$. The computed coefficients match.

Worked Example: Disconnected Edges and an Isolated Vertex

Let $G$ have $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{12,34\}$. Here $n=5$, $m=2$, and $t=0$. The coefficient of $q^3$ is $\binom{2}{2}-0=1-0=1$, so the first three degree positions are $q^5-2q^4+q^3$.

For a direct count, vertices $1$ and $2$ form one edge and have $q(q-1)$ colorings. Vertices $3$ and $4$ form another edge and have $q(q-1)$ colorings. Isolated vertex $5$ can be colored in $q$ ways. The choices are independent, so $P_G(q)=q^3(q-1)^2=q^3(q^2-2q+1)=q^5-2q^4+q^3$. This also checks that disconnected components and isolated vertices are included in the formula.

Why the Triangle Correction Matters

The term $\binom{m}{2}$ counts every pair of distinct edges. Any such pair lowers the number of components by two, whether the edges are adjacent or disjoint. But a triangle contributes an additional three-edge subset with the same component count, and inclusion–exclusion assigns that subset a negative sign. This is exactly why the triangle count is subtracted.

A common mistake is to use $\binom{m}{2}$ alone for the coefficient of $q^{n-2}$. For the triangle $G$ with $V(G)=\{1,2,3\}$ and $E(G)=\{12,23,13\}$, we have $n=3$, $m=3$, and $t=1$. Omitting the correction gives $\binom{3}{2}=3$ as the coefficient of $q$. The correct coefficient is $\binom{3}{2}-1=3-1=2$, and direct counting gives $P_G(q)=q(q-1)(q-2)=q^3-3q^2+2q$. The missing unit comes from the three-edge subset consisting of the entire triangle.

These coefficients depend only on $n$, $m$, and $t$, but lower-degree coefficients can involve larger edge subsets and more detailed structure. The formula is a precise statement about the highest three degree positions, not a method for recovering the entire chromatic polynomial from the number of edges and triangles.

Check Your Understanding

Use the inclusion–exclusion formula and the highest-degree coefficient result to justify your answers.

For a simple graph with $n\ge2$, $m=6$, and $t=2$, what is the coefficient of $q^{n-2}$?
Explain why every two-edge subset of a simple graph contributes to the coefficient of $q^{n-2}$.
What condition must a three-edge subset satisfy to contribute to that same coefficient?
Find the first three degree positions for the graph with $V(G)=\{1,2,3,4\}$ and $E(G)=\{12,23,34,41\}$.
State the chromatic polynomial for the graph with no vertices, and explain why the theorem’s three-term formula is stated for $n\ge2$.