Introduction to Graph Theory (30 page)

Theorem 17
.
Every planar graph having a vertex of degree
≤ 4
has X
≤ 4.

Proof
. Imitate the proof of the Five Color Theorem.

Since the existence of planar graphs with all degrees ≥ 5 is what blocks the most natural avenue to a proof of the Four Color Conjecture, these graphs take on a special significance as test cases. They are the only planar graphs that could possibly have
X
= 5.

Coloring maps

Figure 123a
is a map of South America. Letting borders be “edges” and border junctions be “vertices” we can interpret the map as a planar graph, which graph is isomorphic to the graph of
Figure 123b
. In a similar fashion any other map, actual or imaginary, can be interpreted as a planar graph. Conversely any planar graph can be interpreted as a map, usually an imaginary one, by letting the faces, including the infinite face, be “countries”. If your imagination balks at having a country surround several others, think of the infinite face as an “ocean”. Under these interpretations maps and planar graphs are the same things.

Figure 123

Mapmakers usually color their maps in such a way that countries— including the ocean as a “country”—sharing a border have different colors. Since the cost of printing a map goes up with the number of colors used, mapmakers are naturally interested in knowing the minimum number of colors with which a given map can be colored. Generalizing a bit we are led to consider the following problem.

Map coloring problem
.
Find the smallest number
m
such that the faces of every planar graph can be colored with
m
or fewer colors in such a way that faces sharing a border have different colors.

By “faces sharing a border” we mean faces having one or more edges in common. If two faces have only a vertex or vertices in common we will allow them to have the same color. This is analogous, for example, to maps of the United States in which Utah and New Mexico have the same color.

Notice that this problem is different from the one we have considered previously in this chapter, for now we are coloring the faces, not the vertices, of planar graphs.

The Map Coloring Problem can almost be solved, and the “almost-solution” is that either
m
= 4 or
m
= 5. We shall now derive this.

Let
G
be a planar graph. Select a point within each face of
G
and let two such points be connected by a line whenever the corresponding faces of
G
share a border. As we have seen in
Exercise 8
of Chapter 5, this system of points and lines constitutes a graph, called a
dual graph
of
G
, which is always planar and connected.
Figure 124a
shows a planar graph
G
with a dual drawn within it; the dual has been redrawn in
Figure 124b
.

Suppose that the faces of
G
are colored in such a way that faces sharing a border have different colors. If “
D
” denotes a graph dual to
G
and each vertex of
D
is given the color of the corresponding face of
G
, the result is a coloring of
D
in the sense of
Definition 27
. Conversely a coloring of the vertices of
D
in the sense of
Definition 27
induces a face-coloring of
G
in the sense that faces sharing a border have different colors.

Figure 124

Thus the problem of coloring the faces of planar graphs
G
reduces to the problem of coloring the vertices of the corresponding planar graphs
D
. Since the Five Color Theorem guarantees that five colors are enough to color the vertices of every planar graph, we know that the number
m
exists and in fact
m
≤ 5. Also,
m
≥ 4 because there are planar graphs, for instance
K
₄
, that require four colors in order that faces sharing a border have different colors. Thus we have a partial solution to the Map Coloring Problem:

If the Four Color Conjecture is true,
m
= 4; if not,
m
= 5.

Hence a mapmaker's paint box need contain only five colors. The mapmaker can rest assured that he or she will always be able to cope, no matter how crazily political boundaries are redrawn.

Opposed to our somewhat idealized mapmakers there are real mapmakers, who work under at least two added restrictions. First, when a country is in two or more pieces like the United States the same color is used for each piece.° Second, only oceans and lakes are colored blue. In our statement of the Map Coloring Problem we omitted both restrictions for the sake of simplicity. Including them makes the problem considerably more complex. For example,
Figure 125a
depicts an island on which there are five countries, one of them in two pieces. By the first restriction, both pieces of Ropia must have the same color, so the island requires five colors in all, and because of the second restriction a sixth must be used for the ocean (see
Figure 125b
). So our conclusion that a mapmaker's paint box needs only five colors is correct only for the somewhat unorthodox mapmakers who abide by neither restriction.

Figure 125

Incidentally, when the Four Color Conjecture was first stated in 1852 it was stated in terms of coloring the faces of planar, in fact polygonal, graphs. See the introduction to Ore's
The Four-Color Problem
.

Exercises

1.
  
Find
X
for each of the following graphs:
C
_v
,
W
_v
(see Chapter 2,
Exercise 6
),
UG
, octahedron, dodecahedron, icosahedron. As I remarked on page 136, the icosahedron is a “test case” for the Four Color Conjecture.

  
2
.
  
Find
X
for each of the graphs in
Figure 126
.

Figure 126

  
3
.
  
Obviously the set of all graphs with
X
= 1 is equal to the set of all null graphs
N
_v
. We might call this the “One Color Theorem”. Prove the Two Color Theorem: the set of all graphs with
X
= 2 is equal to the set of all graphs having at least one edge and no odd cyclic subgraphs. (Note: a cyclic graph
C
_v
is called “odd” if
v
is an odd number and “even” if
v
is an even number.) If only there were a “Three Color Theorem” the Four Color Conjecture would be practically resolved. For this reason much of today's four-color research is directed toward finding a characterization of graphs with
X
= 3 analogous to the Two Color Theorem.

4.
  
K
₃
has
X
= 3, so every supergraph of
K
₃
has
X
≥ 3. On the other hand
C
₅
is a graph with
X
= 3 that is not a supergraph of
K
₃
. Find a graph with
X
= 4 that is not a supergraph of
K
₃
.

  
5
.
  
If a graph
G
has chromatic number
X
and its complement
G
has chromatic number
X
, prove that
X
X
≥
v
. Then use the fact that
whenever
m
and
n
are positive integers to prove that
X
+
X
≥ 2√
v
.

  
6.
  
Find a graph for which
X
X
=
v
, and a graph for which
X
+
X
= 2√
v
. Could a single graph satisfy both equations? (If a graph has chromatic number
X
then “
X
” denotes the chromatic number of its complement.)

7.
  
Obviously the Four Color Conjecture is true for planar graphs with four vertices or less. Of the graphs with five vertices only the complete graph
K
₅
has
X
= 5;
K
₅
is nonplanar so the Four Color Conjecture is true for planar graphs with five vertices. To prove that the Four Color Conjecture is true for planar graphs with six vertices we argue as follows:
K
₆
is regular of degree 5, but is nonplanar; every other graph with six vertices has at least one vertex of degree ≤ 4; in particular, therefore, every planar graph with six vertices has at least one vertex of degree ≤ 4, and so has
X
≤ 4 by
Theorem 17
. Prove that the Four Color Conjecture is true for planar graphs with seven vertices.