Introduction to Graph Theory (29 page)

That is, we have to prove that every planar graph with one vertex has
X
≤ 5. The only planar graph, indeed the only graph, with one vertex is
N
₁
, and for this graph
X
= 1.

We might note in passing that
S
is just as clearly true for
v
= 2, 3, 4, or 5 since the chromatic number of a graph cannot exceed its number of vertices.

We are thus given that every planar graph with
k
vertices has
X
≤ 5, and the task is to deduce that every planar graph with
k
+ 1 vertices has
X
≤ 5. So let
G
be an arbitrary planar graph having
k
+ 1 vertices, and we shall do our best to prove that
G
has
X
≤ 5.

Corollary 13
(page 108) guarantees that
G
possesses at least one vertex, call it “
A
”, such that the degree of
A
is ≤ 5. Denote by “
G
−
A
” the subgraph of
G
obtained by erasing vertex
A
and all edges incident to vertex
A
. Then
G
−
A
is a planar graph having
k
vertices. We are given that all such graphs have
X
≤ 5. So
G
−
A
can be colored with five colors or less. Suppose that this has been done. All that remains is to extend the coloring of
G
−
A
with at most five colors to a coloring of
G
with at most five colors.

Case 1
.
G
−
A
has
X
< 5.

In this case
G
−
A
has been colored with at most four colors so
G
, which is obtained from
G
−
A
by restoring vertex
A
and its incident edges, can certainly be colored with at most five. Simply color vertex
A
with a color not used for
G
−
A
.

Case 2
.
G
−
A
has
X
= 5 and
A
has degree < 5.

In this case, vertex
A
is adjacent to at most four vertices of
G
. Color vertex
A
with a color not used for its adjacent vertices, and the result is a coloring of
G
with five colors.

Case 3
.
G
−
A
has
X
= 5 and
A
has degree 5.

Let
P
,
Q
,
R
,
S
, and
T
be the five vertices adjacent to
A
. If any two of these five vertices have been colored with the same color, then there is a color available for
A
and we have a coloring of
G
with five colors. So we may as well assume that
P
,
Q
,
R
,
S
, and
T
have been colored respectively with five different colors 1, 2, 3, 4, and 5.

This case is the difficult one. Now there is no obvious way of coloring vertex
A
without resort to a sixth color. It can be done, however, if we can recolor one of the vertices adjacent to A without unduly upsetting the coloring of
G
−
A
.

Subcase i of case 3
. There is no walk joining
P
to
R
consisting entirely of vertices colored 1 or 3.

Figure 119
depicts what the relevant portion of
G
might look like. In the figure it is assumed that all the walks touching either
P
or
R
, and consisting entirely of vertices colored 1 or 3, are shown. Note that there is no way of getting from
P
to
R
by travelling along such a walk.

Recolor
P
with color 3, and interchange the colors of the vertices of all color 1-color 3 walks touching
P
. This has been done in
Figure 120
. Because of the assumption under which we are working,
R
and the vertices of the color 1-color 3 walks touching
R
are unaffected by this. Now color 1 has been freed for vertex
A
and we have a coloring of
G
with five colors.

Figure 119. Relevant portion of
G
in subcase i of case 3

Figure 120. Same portion after color interchange

Subcase ii of case 3
. There is a walk joining
P
to
R
consisting entirely of vertices colored 1 or 3.

The trick of the last subcase won't work this time, for recoloring
P
with color 3 will force a recoloring of
R
with color 1, and vertex
A
will still be adjacent to five differently colored vertices.

Figure 121
depicts what the relevant portion of
G
might look like. In the figure it is assumed that all walks touching either
Q
or
S
, and consisting entirely of vertices colored 2 or 4, are shown. Note that there is no color 2-color 4 walk joining
Q
to
S
. That this is necessarily so can be seen by the following argument.

Figure 121. Relevant portion of
G
in subcase ii of case 3

G
is planar, so we may as well assume that our drawings have no edge-crossings. Vertex
Q
is surrounded by a cyclic subgraph of
G
—
PUWXYRAP
in
Figure 121
—none of whose vertices is colored 2 or 4; vertex
A
is not colored at all, and the others have been colored 1 or 3. Since
G
is planar any color 2-color 4 walk joining
Q
to
S
must pass through one of the vertices of this cyclic subgraph (by the Jordan Curve Theorem). But no vertex of the cyclic subgraph has been colored 2 or 4, thus there is no walk joining
Q
to
S
consisting entirely of vertices colored 2 or 4.

Now we can use the trick of the last subcase to recolor vertex
Q
with color 4, interchanging the colors of the color 2-color 4 walks touching
Q
accordingly. Vertex
S
will be unaffected by this recoloring, so vertex
A
can be colored with color 2 and we have a coloring of
G
with five colors—see
Figure 122
.

Figure 122. Same portion after color interchange

G
was an arbitrary planar graph with
v
=
k
+ 1. In each case we have shown that
G
can be colored with at most five colors, so
G
has
X
≤ 5. This completes the proof of statement (2) and we're finished.

The key to the proof of the Five Color Theorem is Euler's Formula, though the length of the proof and the number of intermediary theorems makes this easy to overlook. The substance of the proof is of course the proof of statement (2). Our proof of statement (2) depends entirely on knowing that
G
has a vertex of degree less than or equal to 5. This is
Corollary 13
, which we derived from
Theorem 13
; and
Theorem 13
is a derivative of
Theorem 11
, which is in turn a derivative of Euler's Formula.

It's clear that if the Four Color Conjecture is ever proved, the proof will be substantially different from the proof of the Five Color Theorem and not merely modeled on it. For to try to prove the Four Color Conjecture by imitating the proof of the Five Color Theorem, we would need the following analog of
Corollary 13
—“every planar graph has at least one vertex with degree less than or equal to 4”; but as we mentioned in
Exercise 9
of Chapter 4, that statement is false—for example, the icosahedron is a planar graph, but every vertex has degree 5. Imitating the proof of the Five Color Theorem is not entirely fruitless, however, for by doing so we can prove the following more modest theorem, which tells us where to look for counterexamples to the Four Color Conjecture.