1. Introduction
Consider a simple graph $G$, namely one in which every edge connects distinct vertices and no two edges join the same pair of vertices. Throughout, graph means simple graph. Let $V(G)$ denote the set of vertices of $G$, $E(G)$ denote the set of edges of $G$. A graph $H$ is a subgraph of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. A subgraph $H$ of $G$ is a spanning subgraph if $V(H)=V(G)$. A $\lambda$-vertex-coloring of $G$ is an assignment of $\lambda$ colors to the vertices of $G$; the coloring is ‘proper’ if no two distinct adjacent vertices have the same color. $G$ is $\lambda$-vertex-colorable or $\lambda$-colorable if $G$ has a proper $\lambda$-vertex-coloring.
2. Chromatic polynomial of a graph
Let $G$ be a finite graph. For each positive integer $\lambda$, let $P_G(\lambda)$ denote the number of proper colorings of $G$ using $\lambda$ available colors.
At this point $P_G(\lambda)$ is simply a counting function defined for positive integers $\lambda$. We shall first show, by a simple recursive argument, that this function is in fact given by a polynomial in $\lambda$.
2.1 Deletion and contraction
Theorem 1 (Deletion–contraction). For every edge $e$ of $G$,
\[\boxed{ P_G(\lambda) = P_{G{-}e}(\lambda)-P_{G/e}(\lambda). }\]
Proof.
Let $e=uv$. Consider the proper $\lambda$-colorings of $G{-}e$.
Since the edge $uv$ has been deleted, the vertices $u$ and $v$ are not required to receive different colors. Thus every proper coloring of $G{-}e$ falls into exactly one of two classes:
\[\text{$u$ and $v$ receive different colors,}\]or
\[\text{$u$ and $v$ receive the same color.}\]If $u$ and $v$ receive different colors, then restoring the edge $e=uv$ causes no conflict. Hence these colorings are precisely the proper colorings of $G$. Their number is therefore
\[P_G(\lambda).\]Now consider the colorings of $G{-}e$ in which $u$ and $v$ receive the same color. Since they already have the same color, we may identify $u$ and $v$ as a single vertex. This gives exactly a proper coloring of the contracted graph $G/e$.
Conversely, every proper coloring of $G/e$ gives a coloring of $G{-}e$ in which $u$ and $v$ receive the same color, simply by giving both $u$ and $v$ the color assigned to the contracted vertex.
Thus there is a bijection between
\[\{\text{proper colorings of $G{-}e$ with $u$ and $v$ the same color}\}\]and
\[\{\text{proper colorings of $G/e$}\}.\]Hence the colorings in which $u$ and $v$ receive the same color are counted by
\[P_{G/e}(\lambda).\]Since the two classes are disjoint and together contain all proper colorings of $G{-}e$,
\[P_{G{-}e}(\lambda) = P_G(\lambda)+P_{G/e}(\lambda).\]Rearranging gives
\[P_G(\lambda) = P_{G{-}e}(\lambda)-P_{G/e}(\lambda).\]$\blacksquare$
The deletion–contraction relation immediately explains why $P_G(\lambda)$ is a polynomial.
Theorem 2. For every finite graph $G$, the function $P_G(\lambda)$ is given by a polynomial in $\lambda$ with integer coefficients.
Proof.
We use induction on the number of edges of $G$.
If $G$ has no edges and has $n$ vertices, then every assignment of colors to the vertices is proper. Hence
\[P_G(\lambda)=\lambda^n,\]which is a polynomial.
Now suppose that every graph with fewer than $m$ edges has a counting function that is a polynomial in $\lambda$ with integer coefficients, and let $G$ have $m$ edges. Choose any edge $e$.
Both $G{-}e$ and $G/e$ have fewer than $m$ edges. Therefore, by the induction hypothesis,
\[P_{G{-}e}(\lambda)\]and
\[P_{G/e}(\lambda)\]are polynomials in $\lambda$ with integer coefficients.
By deletion–contraction,
\[P_G(\lambda) = P_{G{-}e}(\lambda)-P_{G/e}(\lambda),\]and so $P_G(\lambda)$ is also a polynomial in $\lambda$ with integer coefficients.
The result follows by induction.
$\blacksquare$
We may therefore call $P_G(\lambda)$ the chromatic polynomial of $G$.
2.2 Inclusion–Exclusion
Deletion–contraction proves the existence of the chromatic polynomial in a particularly simple way. For Whitney’s broken-circuit theorem, however, we shall need more than the fact that $P_G(\lambda)$ is a polynomial: we shall need an explicit expression for its coefficients in terms of subsets of the edge set.
That expression follows naturally from the inclusion–exclusion principle.
Theorem 3. Let $G$ be a finite graph with vertex set $V$ and edge set $E$. Then
\[\boxed{ P_G(\lambda) = \sum_{F\subseteq E} (-1)^{|F|}\lambda^{c(F)}, }\]where $c(F)$ denotes the number of connected components of the spanning subgraph $(V(G),F)$.
Proof.
There are $\lambda^{\lvert V\rvert}$ possible assignments of $\lambda$ colors to the vertices of $G$.
For each edge $e=uv\in E$, let $A_e$ be the set of colorings of $G$ in which the endpoints $u$ and $v$ receive the same color. Thus $A_e$ is the set of colorings that fail to be proper on the edge $e$.
A coloring of $G$ is proper if and only if it belongs to none of the sets $A_e$. Hence
\[P_G(\lambda) = \left| \bigcap_{e\in E} A_e^c \right|.\]By De Morgan’s law,
\[\bigcap_{e\in E} A_e^c = \left( \bigcup_{e\in E} A_e \right)^c.\]If the total set of all $\lambda$-colorings is $X$, then
\[\left| \left( \bigcup_{e\in E} A_e \right)^c \right| = |X| - \left| \bigcup_{e\in E} A_e \right|\]and $\lvert X\rvert=\lambda^{\lvert V\rvert}$. Therefore
\[P_G(\lambda) = \lambda^{|V|} - \left| \bigcup_{e\in E} A_e \right|.\]So the sentence means exactly:
Number of proper colorings = Number of all colorings minus number of colorings bad on at least one edge.
Now using inclusion–exclusion principle on $\bigcup_{e\in E}A_e$, we obtain
\[\left| \bigcup_{e\in E} A_e \right| = \sum_{e\in E}|A_e| - \sum_{\{e_1,e_2\}\subseteq E} |A_{e_1}\cap A_{e_2}| + \sum_{\{e_1,e_2,e_3\}\subseteq E} |A_{e_1}\cap A_{e_2}\cap A_{e_3}| -\cdots.\]Thus
\[P_G(\lambda) = \lambda^{|V|} - \sum_{e\in E}|A_e| + \sum_{\{e_1,e_2\}\subseteq E} |A_{e_1}\cap A_{e_2}| - \sum_{\{e_1,e_2,e_3\}\subseteq E} |A_{e_1}\cap A_{e_2}\cap A_{e_3}| +\cdots.\]This may be written compactly as
\[\boxed{ P_G(\lambda) = \sum_{F\subseteq E} (-1)^{|F|} \left| \bigcap_{e\in F}A_e \right| }.\]Here, when $F=\varnothing$, we use the convention that
\[\bigcap_{e\in\varnothing}A_e\]is the set of all $\lambda$-colorings of $V$. Hence the term corresponding to $F=\varnothing$ is
\[\lambda^{|V|}.\]Now fix a subset $F\subseteq E$. A coloring belongs to
\[\bigcap_{e\in F}A_e\]if and only if the two endpoints of every edge in $F$ receive the same color.
Consider the spanning subgraph $(V,F)$. If two vertices lie in the same connected component of $(V,F)$, then they are joined by a path consisting of edges of $F$. Since the endpoints of every edge in that path must have the same color, all vertices in the component must have the same color.
Conversely, each connected component of $(V,F)$ may be assigned a color independently of the other components.
If $c(F)$ denotes the number of connected components of the spanning subgraph $(V(G),F)$, then
\[\left| \bigcap_{e\in F}A_e \right| = \lambda^{c(F)}.\]Substituting this into the preceding formula gives
\[\boxed{ P_G(\lambda) = \sum_{F\subseteq E} (-1)^{|F|} \lambda^{c(F)} .}\]This is the inclusion–exclusion formula for the chromatic polynomial.
$\blacksquare$
3. Broken-circuit-free sets
In a finite graph $G$, fix a linear ordering of the edges of $G$. Thus, if
\[E(G)=\{e_1,e_2,\ldots,e_m\},\]we may suppose that
\[e_1<e_2<\cdots<e_m.\]Definition 1. If $C$ is a cycle of $G$, let $e$ be the largest edge of $C$. The set
\[C-\{e\}\]is called a broken circuit.
The adjective “largest” refers only to the chosen ordering of the edges; it has nothing to do with geometric length.
For example, if a cycle has edge set
\[C=\{e_2,e_5,e_7,e_9\},\]then its largest edge is $e_9$, and the corresponding broken circuit is
\[\{e_2,e_5,e_7\}.\]An edge set $F\subseteq E(G)$ is called broken-circuit-free if it contains no broken circuit.
Example 1 (Broken-circuit-free sets in a square with one diagonal).
Consider the graph $G$ with vertices $v_1,v_2,v_3,v_4$, consisting of the square $v_1v_2v_3v_4v_1$ together with the diagonal $v_1v_3$. Label the edges
\[e_1=v_1v_2,\qquad e_2=v_2v_3,\qquad e_3=v_3v_4,\qquad e_4=v_4v_1,\qquad e_5=v_1v_3,\]and order them by
\[e_1<e_2<e_3<e_4<e_5.\]There are three cycles.
The triangle $v_1v_2v_3v_1$ has edge set
\[\{e_1,e_2,e_5\}.\]Its largest edge is $e_5$, so it gives the broken circuit
\[\{e_1,e_2\}.\]The triangle $v_1v_3v_4v_1$ has edge set
\[\{e_3,e_4,e_5\}.\]Again the largest edge is $e_5$, giving the broken circuit
\[\{e_3,e_4\}.\]Finally, the square itself has edge set
\[\{e_1,e_2,e_3,e_4\}.\]Its largest edge is $e_4$, so it gives the broken circuit
\[\{e_1,e_2,e_3\}.\]Notice, however, that this last broken circuit already contains the smaller broken circuit $\lbrace e_1,e_2\rbrace$. Thus an edge set is broken-circuit-free precisely when it contains neither
\[\{e_1,e_2\}\]nor
\[\{e_3,e_4\}.\]We can therefore count the broken-circuit-free sets by size.
There is one with no edges:
\[b_0=1.\]Every one-edge set is broken-circuit-free, so
\[b_1=5.\]Of the $\binom52=10$ two-edge sets, exactly two are broken circuits, namely
\[\{e_1,e_2\} \quad\text{and}\quad \{e_3,e_4\}.\]Hence
\[b_2=10-2=8.\]Among the three-edge sets, exactly four contain neither forbidden pair:
\[\{e_1,e_3,e_5\},\qquad \{e_1,e_4,e_5\},\qquad \{e_2,e_3,e_5\},\qquad \{e_2,e_4,e_5\}.\]Thus
\[b_3=4.\]There are no larger broken-circuit-free sets.
So the numbers of broken-circuit-free sets of the various sizes are
\[\boxed{1,5,8,4}.\]
The preceding example illustrates a simple but important general fact.
Proposition 1. Every subset of a broken-circuit-free set is itself broken-circuit-free.
Proof.
Let $F\subseteq E(G)$ be broken-circuit-free, and suppose that $F’\subseteq F$. If $F’$ contained a broken circuit, then that same broken circuit would also be contained in $F$, contradicting the assumption that $F$ is broken-circuit-free.
$\blacksquare$
Thus the broken-circuit-free subsets of $E(G)$ form a simplicial complex: whenever a set belongs to the family, all of its subsets belong to the family as well. This simplicial complex is called the broken-circuit complex of $G$, with respect to the chosen ordering of the edges.
We now show that in a connected graph this family is large enough to contain sets of every possible forest size.
Proposition 2. Broken-circuit-free sets exist for every $0\leq i \leq n-1$ in a connected graph on $n$ vertices.
Proof.
Suppose the connected graph has $m$ edges. Assign the edges ranks $1,2,\ldots,m$ according to
\[e_1<e_2<\cdots< e_m,\]and choose a spanning tree $T$ for which the sum of the ranks of its edges is as large as possible. If $T$ contained $C-\lbrace e\rbrace$, with $e$ the largest edge of $C$, then $e\notin T$. Replace any $f\in C-\lbrace e\rbrace$ by $e$. Since $e>f$, the rank sum strictly increases – a contradiction. Thus a broken-circuit-free spanning tree exists. By Proposition 1, every subset of this tree is broken-circuit-free. Hence, by taking $i$-edge subsets of the tree, broken-circuit-free sets exist for every $0\leq i\leq n-1$.
$\blacksquare$
Definition 2. Suppose $F\subseteq E(G)$ contains a broken circuit. Call an edge $e$ ‘eligible for $F$’ if there is a cycle $C$ such that $e$ is the largest edge of $C$ and
\[C-\{e\}\subseteq F.\]The smallest edge eligible for $F$ is called $e(F)$.
4. Whitney’s Broken-Circuit Theorem
Proposition 3 (The broken-circuit pairing). Let $G$ be a finite graph with a fixed linear ordering of its edges. Suppose $F\subseteq E(G)$ contains a broken circuit. Define
\[F' = F\triangle\{e(F)\} = \begin{cases} F\cup\{e(F)\}, & e(F)\notin F,\\ F-\{e(F)\}, & e(F)\in F. \end{cases}\](So the $\triangle$ denotes symmetric difference.)
Then
\[c(F')=c(F),\] \[(-1)^{|F'|}=-(-1)^{|F|},\]and
\[e(F')=e(F).\]Consequently,
\[F\longmapsto F\triangle\{e(F)\}\]is a fixed-point-free involution on the family of edge sets containing a broken circuit.
Proof.
Since $e(F)$ is eligible for $F$, there is a cycle $C$ such that $e(F)$ is the largest edge of $C$ and
\[C-\{e(F)\}\subseteq F.\]The endpoints of $e(F)$ are therefore already joined by the remaining edges of $C$. Hence adding or deleting $e(F)$ does not change the number of connected components, so
\[c(F')=c(F).\]Also, $F$ and $F’$ differ by exactly one edge. Therefore
\[|F'|=|F|\pm1,\]and hence
\[(-1)^{|F'|}=-(-1)^{|F|}.\]It remains to show that
\[e(F')=e(F).\]▶ PZoom: Why does the pairing preserve the eligible edge $e(F)$?
Applying the same operation to $F’$ therefore toggles the same edge once more and returns to $F$. Hence the map is an involution. Since $F’\neq F$, it has no fixed points.
$\blacksquare$
Theorem 4 (Whitney’s Broken-Circuit Theorem). Let $G$ be a finite graph with $n$ vertices, and fix a linear ordering of $E(G)$. For each $i\ge 0$, let $b_i$ denote the number of $i$-edge subsets of $E(G)$ that contain no broken circuit. Then
\[\boxed{ P_G(\lambda) = \sum_{i=0}^{n} (-1)^i b_i \lambda^{n-i}. }\]The absolute value of the coefficient of $\lambda^{n-i}$ is the number of $i$-edge subsets containing no broken circuit.
Proof.
We begin with
\[P_G(\lambda) = \sum_{F\subseteq E(G)} (-1)^{|F|}\lambda^{c(F)}.\]By Proposition 3, each edge set $F$ that contains a broken circuit is paired with exactly one other, and the two corresponding terms in the inclusion–exclusion sum cancel.
We are left with
\[P_G(\lambda) = \sum_{\substack{F\subseteq E(G)\\ F\text{ contains no broken circuit}}} (-1)^{|F|}\lambda^{c(F)}.\]Now any subset $F$ containing no broken circuit must be acyclic. Indeed, if $F$ contained a cycle $C$, then deleting the largest edge of $C$ would produce a broken circuit contained in $F$, a contradiction.
Thus every surviving $F$ is a forest.
If $G$ has $n$ vertices and the forest $F$ has $i$ edges, then
\[c(F)=n-i.\]▶ PZoom: Why does a forest with $i$ edges have $c(F)=n-i$?
Therefore every surviving $i$-edge subset contributes
\[(-1)^i\lambda^{n-i}.\]If $b_i$ is the number of surviving $i$-edge subsets, that is, the number of $i$-edge subsets containing no broken circuit, then
\[P_G(\lambda) = \sum_{i=0}^{n} (-1)^i b_i\lambda^{n-i}.\]This proves Whitney’s broken-circuit theorem.
$\blacksquare$
5. What the coefficients reveal
Whitney’s broken-circuit theorem does more than give another expression for the chromatic polynomial. It gives a direct combinatorial interpretation of its coefficients.
Let $G$ be a finite graph with $n$ vertices, and fix a linear ordering of $E(G)$. For each $i\ge 0$, let $b_i$ denote the number of $i$-edge subsets of $E(G)$ that contain no broken circuit. Whitney’s theorem gives
\[P_G(\lambda) = \sum_{i=0}^{n} (-1)^i b_i\lambda^{n-i},\]with $b_i=0$ whenever no such $i$-edge set exists.
Thus, if
\[P_G(\lambda) = \lambda^n-a_1\lambda^{n-1} +a_2\lambda^{n-2} -a_3\lambda^{n-3} +\cdots,\]then
\[a_i=b_i.\]In words, the absolute value of the coefficient of $\lambda^{n-i}$ is the number of $i$-edge subsets of $E(G)$ that contain no broken circuit.
The example from Section 3 now acquires a new meaning. For the square with one diagonal, we found
\[b_0=1,\qquad b_1=5,\qquad b_2=8,\qquad b_3=4.\]Whitney’s theorem therefore gives
\[P_G(\lambda) = \lambda^4-5\lambda^3+8\lambda^2-4\lambda.\]Thus the four numbers counted directly in Example 1 reappear exactly as the absolute values of the coefficients of the chromatic polynomial.
The first few coefficients have especially transparent interpretations.
Every one-edge set is broken-circuit-free. Hence, if $G$ has $m$ edges,
\[b_1=m,\]and so
\[[\lambda^{n-1}]P_G(\lambda)=-m.\]Thus the coefficient of $\lambda^{n-1}$ records the number of edges of $G$.
The next coefficient already records more structure. If $t$ denotes the number of triangles of $G$, then
\[b_2=\binom{m}{2}-t.\]▶ PZoom: Why is $b_2=\binom{m}{2}-t$?
Therefore
\[[\lambda^{n-2}]P_G(\lambda) = \binom{m}{2}-t.\]Thus the chromatic polynomial determines both the number of edges and the number of triangles of the graph.
At the other end of the polynomial, suppose that $G$ is connected. An $(n-1)$-edge set containing no broken circuit cannot contain a cycle, since every cycle contains a broken circuit. It is therefore a spanning tree. Hence
\[b_{n-1}\]counts precisely those spanning trees that contain no broken circuit, and
\[[\lambda]P_G(\lambda) = (-1)^{n-1}b_{n-1}.\]This gives a particularly striking interpretation of the linear coefficient: its absolute value counts the broken-circuit-free spanning trees.
There is a subtle point here. The definition of a broken circuit depends on the arbitrary ordering chosen for the edges of $G$, but the coefficients of $P_G(\lambda)$ plainly do not. Consequently, for each $i$, the number $b_i$ is independent of the chosen edge ordering, even though the actual family of broken-circuit-free $i$-edge sets may change when the ordering changes.
This is one of the pleasing surprises of Whitney’s theorem: an arbitrary ordering is introduced in order to expose the cancellation, but the numbers that survive the cancellation are intrinsic invariants of the graph.
Several familiar properties of the chromatic polynomial now follow at once.
First, its coefficients alternate in sign. Since every $b_i$ is a nonnegative integer,
\[P_G(\lambda) = \lambda^n-b_1\lambda^{n-1} +b_2\lambda^{n-2} -\cdots.\]Thus the alternating signs are not an algebraic accident; they reflect the parity of the sizes of broken-circuit-free edge sets.
Second, if $G$ has $c$ connected components, then every broken-circuit-free edge set is a forest. Such a forest has at most
\[n-c\]edges. Hence
\[b_i=0 \qquad\text{for }i>n-c,\]and therefore
\[P_G(\lambda)=\lambda^cQ(\lambda)\]for some polynomial $Q$. In particular,
\[\lambda^c\mid P_G(\lambda).\]For a connected graph, this says that $\lambda$ divides the chromatic polynomial.
Finally, if $G$ is connected, Proposition 2 shows that broken-circuit-free sets exist for every
\[0\le i\le n-1.\]Therefore every coefficient from $\lambda^n$ down to $\lambda$ is nonzero, and the signs strictly alternate.
The broken-circuit theorem thus reveals that the chromatic polynomial encodes a remarkable amount of graph structure. The coefficient of $\lambda^{n-1}$ records the number of edges; the coefficient of $\lambda^{n-2}$ records the number of triangles once the number of edges is known; and, more generally, the coefficient of $\lambda^{n-i}$ counts the $i$-edge subsets that survive Whitney’s broken-circuit cancellation.
Seen in this way, the broken-circuit theorem explains why the chromatic polynomial contains much more information than the number of proper colorings at a particular value of $\lambda$. Its coefficients encode a hierarchy of combinatorial information about the graph itself.