THE CHROMATIC POLYNOMIAL

CODY FOUTS

Abstract. It is shown how to compute the Chromatic Polynomial of a sim-

ple graph utilizing bond lattices and the Möbius Inversion Theorem, which
requires the establishment of a refinement ordering on the bond lattice and an
exploration of the Incidence Algebra on a partially ordered set.

1. Introduction
A common problem in the study of Graph Theory is coloring the vertices of
a graph so that any two connected by a common edge are different colors. The
vertices of the graph in Figure 1 have been colored in the desired manner. This is
called a Proper Coloring of the graph.
Frequently, we are concerned with determining the least number of colors with
which we can achieve a proper coloring on a graph. Furthermore, we want to count
the possible number of different proper colorings on a graph with a given number
of colors. We can calculate each of these values by using a special function that is
associated with each graph, called the Chromatic Polynomial.
For simple graphs, such as the one in Figure 1, the Chromatic Polynomial can
be determined by examining the structure of the graph. For other graphs, it is very
difficult to compute the function in this manner. However, there is a connection
between partially ordered sets and graph theory that helps to simplify the process.
Utilizing subgraphs, lattices, and a special theorem called the Möbius Inversion
Theorem, we determine an algorithm for calculating the Chromatic Polynomial
for any graph we choose.

Figure 1. A simple graph colored so that no two vertices con-

nected by an edge are the same color.
1
2 CODY FOUTS

Figure 2. N3 : A null graph on 3 vertices.

Figure 3. K3 : The complete graph on 3 vertices.

2. Basics of Graph Theory

2.1. Basic Definitions. The basic definitions of Graph Theory, according to Robin
J. Wilson in his book Introduction to Graph Theory, are as follows:
• A graph G consists of a non-empty finite set V (G) of elements called
vertices, and a finite family E(G) of unordered pairs of (not necessarily
distinct) elements of V (G) called edges.
• V (G) is called the vertex set and E(G) is called the edge family of G.
• If an edge is the unordered pair {v, w}, the edge is said to join the vertices
v and w and is labeled vw.
• Two vertices v and w of a graph G are said to be adjacent if there is an
edge vw joining them; the vertices v and w are also said to be incident
with the edge vw.
• The degree of a vertex v of a graph G is the number of edges incident with
v.
• A simple graph is one in which there is at most one edge joining a given
pair of vertices and there are no loops, or edges joining a given vertex with
itself.
• A graph is connected if for each pair of vertices u, v there is a sequence of
vertices v0 , v1 , v2 , . . . vn , where v0 = u and vn = v, such that vi vi+1 is an
edge, where 0 ≤ i ≤ n − 1.
With these definitions, we can now describe specific types of graphs.
• A null graph is one in which the edge family, E(G) is empty. A null graph
of n vertices is denoted by Nn . See Figure 2.
• A complete graph is a simple graph in which each pair of distinct vertices
are adjacent. Complete graphs on n vertices are denoted by Kn . See Figure
3.
 THE CHROMATIC POLYNOMIAL 3

Figure 4. C4 : A cycle graph on 4 vertices.

Figure 5. P3 : A path graph on 3 vertices.

• A connected graph in which the degree of each vertex is 2 is a cycle graph.

A cycle graph of n vertices is denoted by Cn . See Figure 4.
• A path graph on n vertices is the graph obtained when an edge is removed
from the cycle graph Cn . A path graph of n vertices is denoted Pn . See
Figure 5.
Next, we discuss graph coloring. Particularly, we are interested in determining the
number of ways we can color the vertices of a graph with a given number of colors so
that no two adjacent vertices are the same color. The following definitions describe
graph colorings:
• A coloring of a graph G so that adjacent vertices are different colors is
called a Proper Coloring of the graph.
• A graph G is k-colorable if we can assign one of k colors to each vertex
to achieve a proper coloring.
• A graph G is k-chromatic or has chromatic number k if G is k-colorable
but not (k − 1)-colorable. Symbolically, let χ be a function such that
χ(G) = k, where k is the chromatic number of G.
We note that if χ(G) = k, then G is n-colorable for n ≥ k.

2.2. Chromatic Polynomials. Now, we discuss the Chromatic Polynomial of

a graph G. This is a special function that describes the number of ways we can
achieve a proper coloring on a graph G given k colors. If G is a simple graph, we
write PG (k) as the number of ways we can achieve a proper coloring on the vertices
of G given k colors and PG is called the Chromatic Function of G. If k < χ(G),
then PG (k) = 0.
If we want to color the null graph N3 with k colors, we notice that this can be
done k 3 ways because there are k color options for each vertex since no vertex is
adjacent to another (See Figure 6). In general, we know that PNn (k) = k n .
4 CODY FOUTS

Figure 6. Calculating the Chromatic Function of N3 .

Figure 7. Calculating the Chromatic Function of P3 .

Figure 8. Calculating the Chromatic Function of K3 .

For the path graph P3 , we start with an end vertex and note that this vertex
can be colored in k ways. As we move across the graph to the right, each successive
vertex can be colored (k − 1) ways as it cannot be the same color as the vertex to
its left (See Figure 7). Thus, P3 can be colored k(k − 1)2 ways with k colors. In
general, PPn (k) = k(k − 1)n−1 .
For the complete graph K3 , we begin by selecting a random vertex and note that
it can be colored k ways. If we move from this vertex to any other, we notice that
this second one can only be colored k − 1 ways as it is adjacent to the first. The
third and final vertex can only be colored k − 2 ways as it is adjacent to both of the
first two (See Figure 8). As a result, we find that K3 can be colored k(k − 1)(k − 2)
ways with k colors. In general, PKn (k) = k(k − 1)(k − 2) · · · (k − n + 1).
For many graphs, it is very difficult to determine the Chromatic Functions by
analysis of the structure of the graphs, as is done above. However, the following
theorem provides a method for computing these functions by deleting an edge in the
graph and then contracting the vertices connected by this edge. When we contract
two vertices, we identify them as a single vertex and all edges incident with either
vertex become incident with both.
 THE CHROMATIC POLYNOMIAL 5

Figure 9. The figure described in the proof of Theorem 1.

Theorem 1. Let G be a simple graph, and let G − e and G/e, respectively, be

the graphs obtained from G by deleting then contracting an edge e. Then PG (k) =
PG−e (k) − PG/e (k).
Proof. We utilize Figure 9 as a reference. Let e = vw. The number of k-colorings
of G − e in which v and w have different colors is the same with or without edge e
and is thus equal to PG (k). Similarly, the number of k-colorings of G − e in which v
and w are the same color does not change regardless of whether the two vertices are
contracted; this number is thus equal to PG/e (k). We note that the graph G/e may
not be be a simple graph, but because v and w are distinct vertices we know that the
contraction will not create any loops. Also, we can ignore multiple edges between
vertices as this does not affect the calculation of the Chromatic Polynomial (as two
adjacent vertices remain adjacent regardless of the number of edges between them).
As a result, we find that the total number of k-colorings of G−e is PG (k)+PG/e (k).
Subtraction yields PG (k) = PG−e (k) − PG/e (k) as desired. 
We notice that in Figure 9, G and G/e are both complete graphs. As a result, we
can easily compute PG (k) and PG/e (k) based on the algorithm given above. Thus,
PG (k) = k(k − 1)(k − 2)(k − 3) and PG/e (k) = k(k − 1)(k − 2). The Chromatic
Polynomial for G − e is more difficult to compute, however we can use our recursion
formula to find that

PG−e (k) = PG (k)+PG/e (k) = k(k−1)(k−2)(k−3)+k(k−1)(k−2) = k(k−1)(k−2)2 ,

as expected.
With Theorem 1, we can now prove that the Chromatic Function of a graph G
is a polynomial. We note that all of the graphs included in the rest of this paper
are simple graphs, so the following theorem relates strictly to these.
Theorem 2. The Chromatic Function of a simple graph is a polynomial.
Proof. We again utilize Figure 9 as a reference. As we did with G, we pick edges
in G − e and G/e and delete and contract them. We then repeat the process with
the four new graphs we have and so on. The process terminates when all of the
remaining graphs are null graphs. Because the Chromatic Function of a null graph
is a polynomial (PNn (k) = k n ), we see that the Chromatic Function of G is equal
to the sum of a large number of polynomials and must itself be a polynomial. We
thus refer to the Chromatic Function as the Chromatic Polynomial. 
6 CODY FOUTS

If we compare the chromatic polynomials of N3 , P3 , and K3 , we notice that they

have some interesting properties.
PN3 (k) = k 3
PP3 (k) = k(k − 1)2 = k 3 − 2k 2 + k
PK3 (k) = k(k − 1)(k − 2) = k 3 − 3k 2 + 2k.
In each of the polynomials above we notice that there is no constant term. Thus, if
k = 0, P (k) = 0, as we would expect. Also, except in the case of the null graph, we
notice that the sum of the coefficients of each polynomial is 0, which tells us that
P (1) = 0. This, again, is as expected because any graph with more than 1 vertex
and at least one edge cannot be properly colored with only 1 color. Our final two
observations are that the coefficients of these polynomials have alternating signs and
that the absolute value of the coefficient on the term k n−1 is the number of edges
of the graph. We prove that these characteristics are common to the Chromatic
Polynomials of all graphs in Section 8.

3. Partially Ordered Sets

3.1. Basic Definitions and Properties. For some graphs, the method in Theo-
rem 1 is either inefficient or too tedious to use for computing the Chromatic Poly-
nomial. However, we can use partition lattices and a special function called the
Möbius Function to find these polynomials. First, we consider partially ordered
sets.
According to E.A. Bender and J.R. Goldman, a partially ordered set Q = (S, ≤)
is a pair consisting of a set S and a binary relation ≤ on S that satisfies the following
properties:
(1) Reflexivity: For all x ∈ S, x ≤ x.
(2) Antisymmetry: Given any x, y ∈ S, if x ≤ y and y ≤ x, then x = y.
(3) Transitivity: For all x, y, z ∈ S, if x ≤ y and y ≤ z, then x ≤ z.
If the binary relation on the set S is irreflexive, that is for all x ∈ S, x 6≤ x, as well
as antisymmetric and transitive, Q is called a strict partial ordering. We also
note that in a partially ordered set, two elements x and y may be incomparable if
x ≤ y is false and y ≤ x is also false. If for every two elements w and z in a partially
ordered set either w ≤ z is true or z ≤ w is true, then the partially ordered set
is called a linearly ordered set or a chain. An interval [u, v] is the set of all
elements between u and v. Thus, [u, v] = {t ∈ S|u ≤ t ≤ v}. A partially ordered
set is locally finite if every interval contains a finite number of elements.
Two partially ordered sets, (S, ≤) and (S 0 , ≤0 ), are isomorphic if they differ only
by a labeling of their elements and ordering relation; this relationship is written
(S, ≤) ∼= (S 0 , ≤0 ). More specifically, we say that (S, ≤) ∼= (S 0 , ≤0 ) if and only if there
is a one-to-one onto map φ : S → S such that x ≤ y if and only if φ(x) ≤0 φ(y).
0

Now, suppose Q is a partially ordered set and let q and r be elements of Q. If x

is another element of Q such that x ≤ q and x ≤ r, then x is called a lower bound
of q and r. If v is a lower bound of q and r such that x ≤ v for all other lower
bounds x, then v is the greatest lower bound or meet of q and r. Similarly,
an element y such that q ≤ y and r ≤ y is called an upper bound of q and r. If
u is an element such that u ≤ y for all other upper bounds y, then u is the least
upper bound or join of q and r. A partially ordered set with the property that
every pair of elements has a meet and a join is called a lattice. The ordering on a
 THE CHROMATIC POLYNOMIAL 7

Figure 10. The physical representation of the divides lattice on

the set {1, 2, 3, 4, 6, 12}.

lattice can be represented physically, as is the case with the “divides” relation on
the set {1, 2, 3, 4, 6, 12} in Figure 10.
3.2. Partitions. A partition of a set R is defined to be a set of subsets of R which
are disjoint and whose union is R. Each element of a partition is known as a part.
As an example, let R = {1, 2, 3, 4}. Two different partitions of R, which we label
P and Q, are P = {{1, 2}, {3}, {4}} and Q = {{1, 2, 3}, {4}}. Two different parts
in P are {1, 2} and {3}.
Given partitions P and Q of a set R, we can define a relationship between them
in which we say that P is finer than Q if every subset, or part, in P is a subset of
a subset (part) in Q, where P 6= Q. We denote this relationship by P ≺ Q. Also,
within this relationship we say that Q is coarser than P . In our example, we see
that P ≺ Q because {1, 2} ⊆ {1, 2, 3}, {3} ⊆ {1, 2, 3}, and {4} ⊆ {4}.
This relationship is known as the Refinement ordering on the partitions of a
set. In the following theorem, we show that the ordering is actually a strict partial
ordering.
Theorem 3. The Refinement ordering on the partitions of a set R is a strict partial
ordering, that is the following three properties hold: Irreflexivity, for all partitions
P , P 6≺ P ; Antisymmetry, for all partitions P and Q, if P ≺ Q, then Q 6≺ P ; and
Transitivity, for all partitions P , Q, and S, if P ≺ Q and Q ≺ S, then P ≺ S.
Proof. We first prove irreflexivity. This property is given in the definition of the
relationship. If P ≺ Q is true, then P 6= Q; thus, P 6≺ P .
To prove antisymmetry, let P and Q be partitions of a set R such that P ≺ Q.
Now, suppose that Q ≺ P . Let q1 be an arbitrary part of Q. Because Q ≺ P , we
know that there exists some p ∈ P such that q1 ⊆ p. Also, because P ≺ Q, we
know that there exists some q2 ∈ Q such that p ⊆ q2 . By transitivity of ⊆, this
means that q1 ⊆ q2 . However, because Q is a partition, all of its parts are disjoint.
Thus, q1 ⊆ q2 means that q1 = q2 . Now, we have q1 ⊆ p and p ⊆ q1 , which means
that q1 = p. It we choose an arbitrary part p1 in P , we can use a similar argument
to show that p1 = q, where q ∈ Q. We conclude that P = Q. However, this is a
contradiction by irreflexivity. Thus, Q 6≺ P .
8 CODY FOUTS

Figure 11. The partition lattice for the set R.

Now, let P , Q, and S be partitions of a set R such that P ≺ Q and Q ≺ S. We

will prove transitivity by showing that P ≺ S. Let p ∈ P . Then, there exists some
q ∈ Q such that p ⊆ q. Also, because Q ≺ S, there exists some s ∈ S such that
q ⊆ s. By transitivity of ⊆, we have p ⊆ s. We also note that P 6= S because then
we would have P ≺ Q and Q ≺ P , a violation of the property of antisymmetry.
Thus, we conclude P ≺ S. 

For the purposes of the partially ordered sets we will use to compute the Chro-
matic Polynomial, we allow the Refinement Ordering to be reflexive. In this case,
the ordering is denoted  and we can have P  P .
Given all possible partitions of a set R, we can create a partition lattice which
organizes the partitions based on the relationship ≺, with the “finest” partitions
at the bottom of the lattice and the “coarsest” at the top. In the partition, a line
is drawn from the partition P to the partition Q given that P ≺ Q and there does
not exist R such that P ≺ R ≺ Q.
We show that this arrangement of the partitions actually forms a lattice by
demonstrating that for any two partitions P and Q, there exists a meet V and a
join U of the two partitions, where U and V are also partitions of the set R. The
meet V will be a partition of the elements of R such that the element x ∈ R appears
in the part of V that is the intersection of the parts of P and Q in which x appears.
We know such a partition will exist as the partition of R in which every element is
in a separate part is finer than all other partitions. The join U of P and Q will be
the finest partition of R such that such that for all parts pi of P there exists part
ui of U such that pi ⊆ ui and the same is true for all parts qi of Q. We know that
such a partition U must exist as the whole set R is the coarsest partition of the set
and thus coaser than all other partitions. An example of a partition lattice of the
set R = {1, 2, 3} is given in Figure 11.
We now extend the idea of partitions and partition lattices to Graph Theory.
A bond of a graph G is a partition of its vertices such that all vertices in the
same part are connected within the graph (meaning that they are adjacent or there
exists a path between them in the graph that includes only other vertices in the
same part). The set of bonds of a graph form the bond lattice. An example of a
graph and its bond lattice is given in Figure 12.
 THE CHROMATIC POLYNOMIAL 9

Figure 12. A graph and its bond lattice.

The bond of a coloring of a graph is a partition of the vertices such that vertices
in the same part are connected through a monochromatic walk, meaning that
vertices in the same part are colored the same color.

4. Incidence Algebra
4.1. The Zeta and Möbius Functions. Considering a partially ordered set P ,
we now look at functions we can define on this set. A function f on P maps P × P ,
the direct product of the elements of P , to R, the set of real numbers. We can
add and multiply these functions, thus forming an algebra which we refer to as the
Incidence Algebra. For most functions in this Incidence Algebra, f (x, y) = 0 if
x 6≤ y in P .
The most basic of these functions is the Zeta Function. Sometimes referred to
as the Indicator Function, it “indicates” whether or not a ≤ b in the set P . The
function ζ(a, b) is defined as follows:

0 if a 6≤ b
ζ(a, b) =
1 if a ≤ b.
Given the partially ordered set P of n elements and a lattice that displays the
ordering of the set, we use the Zeta function to create an n × n matrix that contains
the values of ζ(a, b) for all a, b in the set P . In this Zeta Matrix, each column and
each row is labeled with the name of an element in P . A particular entry in the
matrix will be ζ(a, b), where a is the element corresponding to the row of the entry
and b is the element corresponding to the column. The Zeta matrix is constructed
so that the elements that appear lower in the lattice correspond to the rows closest
to the top of the matrix and the columns farthest to the left.
To demonstrate this idea, we look at the set P = {a, b, c, d}, with the lattice
given in Figure 13. Using the Zeta Function and this lattice, we construct the Zeta
Matrix in Figure 14.
Another function that we can define on a partially ordered set P is called the
Möbius Function. If a and b are elements of the set P , the Möbius Function
µ(a, b) is defined as follows:

 1 if a = b
µ(a, b) = 0 P if a 6≤ b
− c:a≤c<b µ(a, c) if a < b.

10 CODY FOUTS

Figure 13. The lattice corresponding to the set P .

Figure 14. The Zeta matrix corresponding to the set P .

Figure 15. The Möbius Matrix corresponding to the set P .

Again, given a partially ordered set P of n elements and a lattice that describes
the ordering of the set, we can create an n × n matrix that contains all possible
values of the Möbius Function over the set.PWe call this the Möbius Matrix. We
also note that for any interval [x, y] in P , z:x≤z≤y µ(x, z) = 0.
Once again considering the set P = {a, b, c, d} and its lattice, we use the Möbius
Function to create the Möbius Matrix given in Figure 15.
Considering the Zeta Matrix and the Möbius Matrix of our set P , we notice that
both of these matrices are upper triangular. For all functions f in the Incidence
 THE CHROMATIC POLYNOMIAL 11

Figure 16. The product of the Zeta Matrix and the Möbius Ma-
trix is the identity matrix.

Algebra such that f (x, y) = 0 if x 6≤ y, the corresponding matrix will be upper

triangular. In the case of the Zeta Matrix and the Möbius Matrix, we note in
Figure 16 that they are inverses of one another in the Incidence Algebra as their
product is the identity matrix.

4.2. The Kronecker Delta. The identity matrix in Figure 16 corresponds to

another function defined over the set P : the Kronecker Delta. If a and b are
elements of a partially ordered set P , the Kronecker delta, denoted δ(a, b), is defined
as follows:

0 if a 6= b
δ(a, b) =
1 if a = b.
Because in Figure 16 the Delta Matrix is the product of the Zeta Matrix and Möbius
Matrix, we know that the value of δ(a, d) is equal to the product of the Möbius
Function and the Zeta Function over the interval [a, d].
X
δ(a, d) = µ(a, x) · ζ(x, d).
a≤x≤d

We can understand this relationship by recalling the lattice, given in Figure 13,
corresponding to the ordering of the set (where a 6= d). For all x such that x ≤ d,
ζ(x, d) = 1. Also, δ(a, d) = 0 because a 6= d. Thus, we have the following:
X X
0 = δ(a, d) = µ(a, x) · ζ(x, d) = µ(a, x).
a≤x≤d a≤x≤d
P P
We know a≤x≤d µ(a, x) = 0 because µ(a, d) = − a≤x<d µ(a, x).

5. The Principle of Möbius Inversion

The principle of Möbius Inversion is a critical component of the method of
computing Chromatic Polynomials using bond lattices and the Möbius Function.
12 CODY FOUTS

E.A. Bender and J.R. Goldman describe Möbius inversion as an “overcounting-

undercounting, or sieving, procedure.” We consider a couple of examples that
demonstrate this idea.
FinitePSeries: Let f (n) be a function on the positive integers and let
g(n) = m≤n f (m). Using the idea of Möbius Inversion, we invert this sum in
order to express f (n) in terms of g. We thus find f (n) = g(n) − g(n − 1).
Classical Möbius Inversion:
P Let f (n) be a function defined on the positive
integers and let h(n) = k|n f (k), where k|n is read “k divides n.” Using the
idea of P
Möbius Inversion, we wish to solve for f (n) in terms of h. We find that
f (n) = k|n µ(k, n)h(k).
5.1. The Möbius Inversion Theorem. The Möbius Inversion Theorems formal-
ize the principle of Möbius Inversion and are the key to solving inversion problems.
The following is the Möbius Inversion Theorem I.
Theorem 4. Let Ne (x) (read “N sub equal to”) be a real-valued function defined for
all x in a locally finite partially ordered set (S, ≤) and assume there is an element
m ∈ S such that Ne (x) = 0 when x 6≤ m. Define Na (x) (read “N sub at least”) by
X
Na (x) = Ne (y).
y:y≥x

Then
X
Ne (x) = µ(x, y)Na (y).
y:y≥x
P P
Proof. We first note that Na (x) = y:y≥x Ne (y) = x≤y≤m Ne (y) because Ne (y) =
0 for all y > m. We also see that this sum is finite because our partially ordered
set is locally finite.
Next, we substitute this into the right side of the equation for Ne (x).
X X X
Na (y)µ(x, y) = Ne (z)µ(x, y).
y:y≥x x≤y y≤z≤m
The next step is to notice
X X XX
Ne (z)µ(x, y) = Ne (z)ζ(y, z)µ(x, y)
x≤y y≤z≤m x≤y z
because ζ(y, z) = 0 if y 6≤ z and Ne (z) = 0 if z 6≤ m. Rearranging the summands,
we find
XX X X
Ne (z)ζ(y, z)µ(x, y) = Ne (z) µ(x, y)ζ(y, z).
x≤y z z x≤y
P
However, we know x≤y µ(x, y)ζ(y, z) = δ(x, z). Thus,
X X X
Ne (z) µ(x, y)ζ(y, z) = Ne (z)δ(x, z).
z x≤y z
Because δ(x, z) = 1 when z = x and 0 otherwise, we see that
X
Ne (z)δ(x, z) = Ne (x).
z
 THE CHROMATIC POLYNOMIAL 13

The Möbius Inversion Theorem II is nearly identical to the Möbius Inversion

Theorem I, except that it refers to NA (read “N sub at most”) rather than Na .
Theorem 5. Let Ne (x) be a real-valued function defined for all x in a locally
finite partially ordered set (S, ≤) and assume there is an element l ∈ S such that
Ne (x) = 0 when x 6≥ l. Define NA (x) by
X
NA (x) = Ne (y).
y:y≤x

Then
X
Ne (x) = µ(y, x)NA (y).
y:y≤x

Proof. The proof of this theorem is analogous to the proof of the Möbius Inversion
Theorem I. 

6. Examples of Möbius Inversion

In order to better understand Möbius Inversion, we make a slight diversion to
consider three examples that utilize the Möbius Inversion Theorem. We need the
following definitions to proceed.
If, in a locally finite partially ordered set P , x ≤ y ≤ z ≤ w, then µ(y, z) in P
equals µ(y, z) in [x, w].
Now, let P = (S1 , ≤1 ) and Q = (S2 , ≤2 ) be partially ordered sets. The direct
product Σ = P × Q of P and Q is the partially ordered set (S, ≤), where
(1) S = S1 × S2 = {(a, b)|a ∈ S1 , b ∈ S2 },
(2) a ≤ b in Σ if and only if a1 ≤1 b1 and a2 ≤2 b2 , where a = (a1 , a2 ) and
b = (b1 , b2 ).
From the definition of the direct product, we can understand the Product Theo-
rem.
Product Theorem: If P has Möbius Function µ1 and Q has Möbius Function µ2 ,
then the Möbius Function µ of P × Q is given by

µ((x1 , x2 ), (y1 , y2 )) = µ1 (x1 , y1 )µ2 (x2 , y2 ).

6.1. Connected Graphs. A connected graph is defined as a graph in which, for

any two vertices, there is a walk between them. Using Möbius Inversion, we wish
to count the number of possible connected graphs on a given set of vertices.
We begin by noting that each graph is a union of its connected components. Also,
connected components of a graph G are disjoint and therefore form a partition of
the vertex set of G. This is referred to as the connected component partition of the
graph G.
Let V be a vertex set. Next, for each partition P of V , let N (P) be the number
of graphs whose connected component partition is P. In terms of the Möbius
Inversion Theorem, we think of N (P) as Ne (P). To determine the number of
possible connected graphs on the vertex set, we need to calculate Ne ({V }). We
find the following formula:
14 CODY FOUTS

v
Ne (P) = 2(2) .
X

P:P is a partition of V
The right hand of this formula represents the total number of graphs that we can
construct on the vertex set V of v elements. This is equal to the left side, which
sums the number of graphs having a certain connected component partition over
all possible connected component partitions.
Now, if we consider a specific partition of V , say Q, if we add up Ne (P) for all
partitions P finer than or equal to Q, we should get the total number of graphs
whose connected componenet partitions are contained in Q. This sum is the number
of graphs all of whose edges connect two vertices in one of the parts Ci of Q. By
the product principle, this is the number of graphs all of whose edges are in C1
multiplied by the number of graphs all of whose edges are in C2 multiplied by...etc.
If each Ci has size ci , then
k
ci
2( 2 ) .
X Y
Ne (P) =
P:PQ i=1
Using Möbius Inversion, we find
j
bi
2( 2 )
X Y
Ne (Q) = µ(P, Q)
P:PQ i=1
where bi is the size of the each class Bi for each P. We want N ({V }), so we find
j
bi
2( 2 ) .
X Y
N ({V }) = µ(P, {V })
P:P{V } i=1

Because all partitions of V are finer than {V }, we can use the partition lattice
to compute all the values of the Möbius Function in this formula.
As an example, we consider the vertex set V = {1, 2, 3}. The partition lattice for
this set is the same as the bond lattice for the complete graph on 3 vertices. This
lattice is in Figure 17 with µ(x, {V }) calculated for each partition x in the lattice.
Now, we can use the formula for N ({V }) to find the total possible number of
connected graphs on this vertex set.

j
bi 1 1 1 2 1 3
2( 2 ) = 2(2(2) ·2(2) ·2(2) )−3(2(2) ·2(2) )+1(2(2) ) =
X Y
N ({V }) = µ(P, {V })
P:P{V } i=1
3
2(1) − 3(2) + 2(2) = −4 + 23 = 4.
Thus, there are 4 possible connected graphs on the vertex set V = {1, 2, 3}.
6.2. Classical Möbius Inversion. Using the Möbius Inversion Theorem, we wish
to solve the following problem:
Let f (n) be a function defined on the positive integers and define
X
h(n) = f (k).
k|n
We wish to invert the sum to solve for f (n) in terms of h.
 THE CHROMATIC POLYNOMIAL 15

Figure 17. The partition lattice for the vertex set V = {1, 2, 3}
with the Möbius Function values included.

To continue, we must first consider the set S, the set of integers with the usual
ordering, and the Möbius function defined over S in the following manner:

 1 when n = k
µ(n, k) = −1 when n + 1 = k
0 otherwise.


Now, let n be an integer and define D(n) as a the set of divisors of n. By the
Unique Factorization Theorem, D(n) ∼ = D(pα αs
1 ) × ... × D(ps ), where each pi is
1

α1 αs
a prime and n = p1 · · · ps . Hence, in the Möbius Function, we can calculate µ
on D(pα ). However, D(pα ) is the chain 1|p|p2 · · · |pα , which is isomophic to the
integers in the set S as we can map each pi to i and order the pi with regards to i.
Thus,

 1 when i = j
µ(pi , pj ) = µ(i, j) = −1 when i + 1 = j
0 otherwise.

Now, letQsa and b be integers.Qs We know we can factor a and b into primes so
that a = i=1 pai i and b = i=1 pbi i , where each pj is a prime. By the Product
Theorem,
s
Y s
Y 
µ(a, b) = µ pai i , pbi i
i=1 i=1
P
(bi −ai )

(−1) if bi − ai = 0 or 1 for all i
= µ(pa1 1 , pb11 ) · · · µ(pas s , pbss ) =
0 bi − ai > 1 for some i.
 
b
From this, we can deduce that µ(a, b) = µ 1, a . To understand this result, suppose
px = a and py = b, then py−x = ab . Now, µ(a, b) = µ(px , py ). By the result above
this is nonzero only if x = y or x + 1 = y. However, if x = y, then py−x = p0 ;
if x + 1 = y, then py−x = p. Because 1 = p0 , we see that µ(1, ab ) = µ(p0 ,px−y ),
which is nonzero only if px−y = p0 or px−y = p. Thus, µ(a, b) = µ 1, ab . For
16 CODY FOUTS

convenience, we simply denote µ(1, ab ) as simply µ( ab ). Now for any n, we define

µ(n) as follows:

 1 if n = 1
µ(n) = (−1)k if n is a product of k distinct primes
0 if a square divides n.

Now, using the Möbius Inversion Theorem, we find
X X n
f (n) = µ(k, n)h(k) = µ h(k).
k
k|n k|n

6.3. The Euler Phi-Function. The Euler phi-function, φ(n), for some positive
integer n, is the number of positive integers x less than or equal to n which are
relatively prime to n (in other words, the number of integers x less than or equal to
n such that gcd(n, x) = 1). We will use Möbius Inversion to determine an eloquent
formula for computing φ(n).
In terms of the Möbius Inversion Theorem, let Ne (n) = φ(n). To find NA (n),
we divide the set [n] = {1, 2, ..., n} according to the gcd with n. Thus, let Sd =
{i ∈ [n]|gcd(i, n) = d}. The sets P Sd are mutually disjoint and their union will be
[n]. As a result, we find that n = d|n |Sd |. However, we note i ∈ Sd if and only if
i = kd, where k ≤ i and gcd(k, nd ) = 1. This guarantees that each Sd is mutually
disjoint and also provides a method for computing the elements of Sd . For each
d we compute nd and then determine all k such that gcd(k, nd ) = 1.PFor each k,
the element kd is in Sd . Thus, we note that |Sd | = φ( nd ) and n = d|n φ( nd ) =
0
P
d0 |n φ(d ) = NA (n). Using the Möbius Inversion Formula, we find

X n X n n n n
Ne (n) = φ(n) = µ NA (d) = µ d=n− − − ··· + + ··· ,
d d p1 p2 p1 p2
d|n d|n

where µ( nd ) is non-zero only if n

d is a product of distinct primes. If this is true, then
n
d = p1 ···p i
. Thus, we find
Y 1
φ(n) = n 1− .
p
p|n

7. Möbius Inversion and the Chromatic Polynomial

7.1. Example 1. We now apply the Möbius Inversion Theorem to the problem of
determining the Chromatic Polynomial of a graph.
Let G be the graph given in Figure 18. Based on our figure, we see that the
Chromatic Polynomial of G is PG (k) = k(k − 1)(k − 2)2 = k 4 − 5k 3 + 8k 2 − 4k.
This should be the same result yielded by the Möbius Inversion Theorem.
In order to proceed, we need the bond lattice of the graph G, so that we have
an ordering on the bonds of the vertices of G. The bond lattice is given in Figure
19. Also, we need to define the functions Ne and Na for any bond b. The function
Ne (b) represents the number of colorings on the vertices of G that have exactly b as
their bond representation. The function Na (b) represents the number of colorings
on the vertices of G that have at least b as their bond; that is, all colorings whose
exact bond representation is the same or coarser than b. For any bond b and any
 THE CHROMATIC POLYNOMIAL 17

Figure 18. The graph G and a demonstration of the computation

of its Chromatic Polynomial.

Figure 19. The bond lattice of the graph G.

number of colors k, Na (b) = k i , where i is the number of parts of the bond b.

This is because our only restriction on the coloring is that bonds in the same part
must be the same color; we are not concerned with adjacent vertices or vertices in
different parts colored different colors. As a result, there are are k ways to color
each part of the bond, yielding k i ways to color a bond with i parts.
To calculate the Chromatic Polynomial of G, we need to calculate
Ne ({{1}, {2}, {3}, {4}})
as the bond {{1}, {2}, {3}, {4}} represents all colorings in which no two adjacent
vertices are the same color. Let
P this bond be denoted by P , then by the Möbius
Inversion Theorem, Ne (P ) = Q:P Q µ(P, Q)Na (Q).
As a result, for each bond Q in the lattice, we evaluate µ(P, Q). In our lattice,
we assign each bond its respected value. See Figure 20.
18 CODY FOUTS

Figure 20. The bond lattice of the graph G, with the Möbius
Function values included.

We notice that all bonds on the same level of the lattice have the same number
of parts. Thus, for all bonds Q on the same level, Na (Q) = k i , where i is the
common number of parts. We can then sum up the Möbius Function values for all
the bonds on a particular
P level and use this value as4the coefficient of k i in our sum.
3 2
We find that Ne (P ) = Q:P Q µ(P, Q)Na (Q) = k − 5k + 8k − 4k, which is, in
fact, PG (k).

7.2. Example 2. As a further application of the Möbius Inversion Theorem to

Chromatic Polynomials, we compute the Chromatic Polynomial of the cycle graph
given in Figure 21. In order to accomplish this task, we first set up the bond lattice
of this graph as shown in Figure 22.
As in our previous example, we need to compute

Ne ({{1}, {2}, {3}, {4}, {5}}

in order to find the Chromatic Polynomial of the graph. Let the bond
{{1}, {2}, {3}, {4}, {5}} be represented by r. As before, we must calculate µ(r, p)
for all bonds p in the lattice. For each bond in the lowest two levels, this process
is simple: the finest bond has a value of 1, while each bond in the second level
has value -1. To compute the Möbius Function values for bonds in the third and
fourth levels, we set up mini-lattices for each bond. For example, if we consider the
bond {{1, 4}, {3, 5}, {2}}, we can set up the mini-lattice given in Figure 23, which
contains this bond and all finer bonds. Using the Möbius Function, we find that
µ(r, {{1, 4}, {3, 5}, {2}}) = 1. It can be calculated that every bond in the third
level has a value of 1 under the Möbius Function.
Next, we consider a bond on the fourth level, {{1, 2, 3}, {4, 5}}, and set up a
mini-lattice for this bond in Figure 24. Again using the Möbius Function, we find
that µ(r, {{1, 2, 3}, {4, 5}}) = −1 and that all bonds on this level have a function
value of −1.
To find the function value for the coarsest bond, {1, 2, 3, 4, 5}, we simply sum
together the values for every other bond and then assign this bond the additive
 THE CHROMATIC POLYNOMIAL 19

Figure 21. A cycle graph with 5 vertices.

inverse of this value. Thus, if we sum together all other Möbius Function values,
we find that the sum is −4. As a result, µ(r, {1, 2, 3, 4, 5}) = 4.
We can now fill out our bond lattice with the Möbius Function value for each
bond, as is done in Figure 25. As before, we notice that all bonds that are found on
the same level of the lattice have the same number of parts. Thus, for all bonds p
that occur on the same level, Na (p) = k i , where i is the common number of parts.
Then, we once again sum up the Möbius Function values for all the bonds on a
particular level and
P use this resulting value as the coefficient of k i in our sum. As
a result, Ne (r) = p:r≤p µ(r, p)Na (p) = k − 5k 4 + 10k 3 − 10k 2 + 4k, and we have
5

found the Chromatic Polynomial of the path graph on 5 vertices as desired.

We double-check our answer using Theorem 1. The calculations are given in
Figure 26. From the diagrams, we see that the Chromatic Polynomial is k(k −
1)4 − [k(k − 1)3 − k(k − 1)(k − 2)] = k 5 − 5k 4 + 10k 3 − 10k 2 + 4k, as desired.

8. Characteristics of the Chromatic Polynomial

We now utilize our method of computing Chromatic Polynomials by use of the
bond lattices and the Möbius Inversion Theorem to prove characteristics of the
Chromatic Polynomial.
First, we consider that in the Chromatic Polynomial of a graph of n vertices, the
coefficient of the k n−1 term is always the negative of the number of edges in the
graph. This is because the second level of any bond lattice is composed of bonds
that contain only an edge and singleton vertices. Thus, the number of bonds in
the second level of a bond lattice is always the number of edges of the graph. Also,
because the first level is always composed of only one bond that always has a Möbius
Function value of 1 and is always finer than every bond on the second level, each
bond on the second level will have a function value of -1. Because Na (b) = k n−1
for all bonds b on the second level of any lattice, the coefficient on the k n−1 term
will always be the negative of the number of edges in the graph.
Next, we show why the coefficients in a Chromatic Polynomial always sum to 0.
This is because the Möbius Function value for each bond in the bond lattice of a
graph is calculated so that the function value for a particular bond and function
values of all finer bonds sum to 0. Particularly, the function value for the coarsest
bond in the bond lattice is chosen so that the sum of all function values of all
bonds in the lattice is 0. Also, we note that plugging k = 1 into any Chromatic
Polynomial is the same as summing together all of the coefficients. For any graph
with at least one edge, this sum will always be 0 as such a graph cannot be properly
colored with k = 1 colors.
20 CODY FOUTS

Figure 22. The bond lattice for the path graph with 5 vertices
(Intermediate lines have been removed to avoid confusion).
 THE CHROMATIC POLYNOMIAL 21

Figure 23. The mini-lattice for the bond {{1, 4}, {3, 5}, {2}}.

Figure 24. The mini-lattice for the bond {{1, 2, 3}, {4, 5}}.

To explain why the signs on the coefficients of the Chromatic Polynomial alter-
nate, we utilize an induction proof on the bond lattice of a graph. Our base case is
a bond lattice that consists of only two levels. The lower level will consist of only
the bond in which each vertex is in a separate part; this bond will always have a
Möbius Function value of 1. On the second level, any bond b will have a function
value of −1 because the bond on the first level will be finer than b and this is in
fact that only bond finer than b. Thus, the Chromatic Polynomial for the graph
described by this bond lattice will be k i − jk i−1 , where j is the number of bonds
22 CODY FOUTS

Figure 25. The bond lattice for the path graph with all Möbius
Function values included.
 THE CHROMATIC POLYNOMIAL 23

Figure 26. The calculation of the Chromatic Polynomial for the

path graph using Theorem 1.

on the second level of the lattice. We have thus shown that this Polynomial has
alternating coefficients.
Now, suppose we have a bond lattice that consists of n levels, where n > 2, and
that our result is true for bond lattices of n − 1 levels. If we consider only the first
n − 1 levels of our lattice, we know that the Möbius Function values of the bonds
on different levels alternate in sign. Now, let b be a bond on the nth level of this
lattice. We must show that the Möbius Function value of b is not 0 and that the
sign of the function value is different from the signs of the function values for bonds
on the n − 1 level. We know b will not have a function value of 0 because we only
include bonds in the lattice that correspond to possible subgraphs of the graph we
are considering. Now, suppose b is only coarser than one bond on the n − 1 level,
denoted by c. This is not possible because the Möbius Function value of b would
have to be 0. This would occur because the function value of c is calculated so
that the sum of the function values of all bonds finer than c (which, in this case,
would be all other bonds finer than b) and the function value for c is 0. Thus, there
must be at least 2 bonds on the n − 1 level that are finer than b. Also, the sub-
lattices corresponding to each of these finer bonds must have some sort of overlap,
otherwise the function value for b would again be 0. Because of this overlap, when
we sum together the Möbius Functon values of all bonds finer than b, we will find
that this sum will have the sign of the bonds on the n − 1 level, as these values will
dominate in the sum. Thus, the Möbius Function value for b must have an opposite
sign in order to get the sum back to 0. As a result, we have shown that the signs
of the Möbius Function values in a bond lattice alternate between each level and,
consequently, that the coefficients of the Chromatic Polynomial alternate in sign.
24 CODY FOUTS

Figure 27. The graph J, which is made up of the components G

and H.

The other chracteristic of the Chromatic Polynomial we consider is that the

number of components of a graph determines the power of the lowest term in the
Chromatic Polynomial. First, we must define connected graphs and components
of a graph. A graph is connected if for any two vertices, there is a walk between
them. A component of a graph is a maximal connected subgraph. For example,
in Figure 27, if J is the graph given, then the graphs G and H are components of
J.
Now, suppose L is a graph that is composed of only one component. If we
construct the bond lattice of this graph, we know that it will have h levels, where
h is the number of vertices in the graph. Also, the sum of the Möbius Function
values for the bonds of the jth level of the lattice will correspond to the coefficient
of the k h+1−j term in the Chromatic Polynomial of L. Because the lattice has h
levels, the sum of the Möbius Function values for the highest level, or hth level,
will correspond to to the k h+1−h = k 1 term; this will also be the lowest power of k
in the Chromatic Polynomial.
Now, suppose L has n components. We can determine the Chromatic Polynomial
of each component separately and we know the lowest term of k in each will be k 1 .
To find the Chromatic Polynomial for L, we multiply the Chromatic Polynomials
of all of L’s components together, as any coloring on a particular component will
be independent of the colorings on the other components. This produces a new
polynomial, for which the lowest term of k is k n .

9. Conclusion
We have now shown the connection that exists between Graph Theory and par-
tially ordered sets and this connection has led us to develop a universal method for
computing the Chromatic Polynomial of any graph we choose. The cornerstone of
this method is the Möbius Inversion Theorem. We have seen that this theorem is a
very powerful tool that can be utilized within any combinatorial problem in which
objects are assigned properties. Particularly, we need only to construct the bond
lattice of a given graph and then apply the Möbius Inversion Theorem to find the
Chromatic Polynomial of a given graph.
As further study of this topic, we could explore the calculation of Chromatic
Polynomials given different restrictions on the colorings of a graph. For example,
we could explore colorings for which particular pairs of adjacent vertices are the
same color or colorings for which adjacent vertices are not similar colors. Another
possible topic could be Chromatic Polynomials for edge colorings. Richard Stanley’s
 THE CHROMATIC POLYNOMIAL 25

text Enumerative Combinatorics provides guidance for further exploration of these

ideas.

References
[1] Bender, E.A. and J.R. Goldman. “On the Applications of Mobius Inversion in Com-
binatorial Analysis.” The MAA Mathematical Sciences Digital Library. 4 Nov 2008
(www.joma.org/images/upload library/22/Ford/BenderGoldman.pdf).
[2] Bogart, Kenneth P. Introductory Combinatorics. New York: Harpcourt Academic Press.
2000.
[3] Rota, Gian-Carlo. “On the Foundations of Combinatorial Theory I. Theory of Möbius Func-
tions.” 1964.
[4] Stanley, Richard P. Enumerative Combinatorics. New York: Cambridge University Press.
1999.
[5] Wilson, Robin J. Introduction to Graph Theory. New York: Prentice Hall. 1996.