last edited March 7, 2016

5.5 Map Colorings

In Section 5.4 we considered an application of graph theory for studying polyhe-
dra. In particular, we used Euler’s formula to prove that there can be no more
than five regular polyhedra, which are known as the Platonic Solids. Many clas-
sical philosophers believed in a mystical correspondence between these polyhe-
dra and air, earth, fire, and water – which they understood to be the four basic
elements of the world; the fifth polyhedron corresponds to the universe itself,
or to the ‘aether’. This belief is no longer widespread, but it might be of some
historical or cultural interest to some readers.
We now consider an application of graph theory, and of Euler’s formula, in
studying the problem of how maps can be colored. Map-makers often color adja-
cent geo-political regions di↵erently, so that map-readers can quickly distinguish
distinct regions. In the illustration below on the left, we color Pennsylvania or-
ange, West Virginia yellow, New York purple, and so forth. If we had a box of
64 Crayola crayons, of course we would have enough colors so that every state
could have a distinct color. But if we only have five or six colors, we certainly
can’t color every state a di↵erent color. But maybe we can still color every
adjacent state a di↵erent color. Is that possible? Or, to make this question a
bit more precise – how many colors would we need to make sure that adjacent
states never share a color? This is a classical problem in graph theory, and in
this section we’ll use graph theory, and in particular planar graphs and Euler’s
formula, to study it.

Figure 31: Map of several northeastern states, and a representation of this map
as a planar graph.

To see how graphs can be relevant to studying maps, we construct a new

graph so that each state is represented by a vertex, and so that two vertices
are connected by an edge if and only if the two states share a boundary. The
illustration above on the right shows such a graph. Although it is not entirely
obvious, such a graph is always planar, as crossing edges would indicate crossing
borders between adjacent states, which cannot occur.
Since maps can be represented as planar graphs, if we can prove that some
number of colors is always sufficient to color the vertices of a planar graph, then
we can also know that that number of colors is sufficient to color a map. In

62
 last edited March 7, 2016

what follows, we will prove that 6 colors is always sufficient to color a planar
graph. In fact, 4 colors is also sufficient to color any planar graph, but proving
that statement is quite involved, and would take the remainder of the semester
to investigate. The two papers that proved this theorem in 1976 required well
over a hundred pages, and are well beyond the treatment here. However, we
can still prove that 6 colors are sufficient. Proving that 5 colors is sufficient is
more difficult than proving that 6 are sufficient, but nowhere nearly as difficult
as proving that 4 are sufficient.

Vertices with Small Degree

In order to prove that every planar graph can be colored with 6 colors, we first
need to prove the following theorem:
Theorem 11. Every planar graph contains at least one vertex with degree at
most 5.
Proof. We have previously seen that for an arbitrary graph with v vertices and
e edges, we can calculate e by considering the degrees of all vertices vi . In
particular,
Xv
deg(vi ) = 2e. (55)
i=1
We can use this relationship to write the average degree of a vertex in terms of
e and v. If we take the sum of the degrees and divide that sum by the total
number of vertices, then we can write this average, which we call deg, as:
deg = 2e/v. (56)
We have also considered a similar relationship between the number of edges
in a graph and the degrees of its faces. If we take into account the outside face
of a planar graph, then every edge in a planar graph appears in exactly two
faces. If a graph has f faces, and if we use deg(fi ) to refer to the number of
edges around face fi , then we can write:
f
X
deg(fi ) = 2e. (57)
i=1

Since every face must have at least 3 faces (i.e., deg(fi ) 3 for all faces), then
we can rewrite Equation 57 as an inequality
3f  2e, (58)
or equivalently as
2
f e. (59)
3
We should recall here Euler’s formula for planar graphs which can be written
as:
f =2+e v. (60)

63
 last edited March 7, 2016

Combining the previous two equations, we have:

2
2+e v e. (61)
3
Basic high-school algebra allows us to rearrange this and conclude that:
12
2e/v  6 . (62)
v
We have already seen above that 2e/v is equal to the average degree of a vertex.
In other words, we have:
12
deg  6 . (63)
v
Since v is always a positive number, the quantity 12/v is also always positive,
and so the right-hand side of Equation 63 is a number strictly smaller than 6.
This shows that at least one vertex must have degree smaller than 6, since if the
degree of every vertex was 6 or greater, then this average would be 6 or larger.
We thus conclude that every planar graph has at least one vertex with degree
at most 5.

Every Planar Graph is 6-colorable

Knowing that every planar graph has at least one vertex with degree at most 5
allows us to prove that:
Theorem 12. The vertices of every planar graph can be colored using 6 colors
in such a way that no pair of vertices connected by an edge share the same color.

Proof. We begin by noticing that every graph on 6 or fewer vertices can certainly
be colored with 6 colors, since we can color each vertex with a di↵erent color.
Our challenge is then to consider what happens when we have a graph with 7
or more vertices. Can all graphs with 7 or more vertices be colored with only
6 colors? We use a technique called mathematical induction to show that the
answer to this question is yes. In particular, we show that if every planar graph
with k vertices can be colored using 6 colors, then so too can every planar graph
with k + 1 vertices. By proving this, we in e↵ect show that not only can every
graph with 6 vertices be colored using 6 colors, but so too can every graph with
7 vertices, and every graph with 8 vertices, and every graph with 9 vertices, etc.
How do we prove that if every planar graph with k vertices can be colored
with 6 colors, then so too can every graph with k + 1 colors? Let’s consider
a hypothetical graph G on k + 1 vertices; part of such a graph is illustrated
in Figure 32. We want to show that G can be colored using at most 6 colors.
From Theorem 11 we know that G must have at least one vertex with degree
at most 5. Let us find one of those vertices and call it s. For a moment, let’s
consider what happens when we remove vertex s. We construct a new graph
which is identical to G except that s is now removed; we call this new graph
G0 , to indicate that it’s a modified version of G. Since G had k + 1 vertices and

64
 last edited March 7, 2016

Figure 32: Parts of a graph G with v = k + 1 vertices, and of a modified version,

which we call G0 , obtained by removing the vertex s. After putting back s, it is
clear that we can color it using a color not used by any of its neighbors.

we removed one vertex to create G0 , then G0 must have k vertices. Since we

already know that all graphs with k vertices can be colored with 6 colors, we in
e↵ect know that G0 can be colored using only 6 colors.
What happens when we try to put vertex s back into the graph G0 ? We
know that s has no more than 5 neighbors, meaning that at most 5 other colors
are being used nearby to vertex s. This means that we can find a sixth color not
shared by any neighbors of s, and which we can use to color s. Upon restoring
s to our graph and coloring it that final color, we obtain our original graph G
that we now know can be colored using only 6 colors.
This shows that if all planar graphs with k vertices can be colored using 6
colors, then so can all planar graphs with k + 1 vertices. Since we know that all
graphs on 6 vertices can be colored with at most 6 colors, we then also know that
all graphs with 7 vertices, and 8 vertices, and 9 vertices, etc, can also be colored
in such a way. This completes our proof by induction of the theorem.
It is also possible to prove in a reasonable short space that every planar
graph can be colored with only 5 colors, though we do not consider that proof
here. As we have noted earlier, it is actually true that every map can be colored
using only 4 colors, but the proof of that statement is very complicated and well
beyond the tools we have developed so far.

65