Introduction to Graph Theory (37 page)

Figure 141 .

Figure 142.
Q
on
S
₁
without edge-crossings
(top view; vertices 9–16 and dotted edges are underneath).

The Heawood Coloring Theorem

Definition 33.
If
n
≥ 0 is an integer then the
chromatic number of the surface
S
_n
denoted “X
(
S
_n
)”, is the largest among the chromatic numbers of graphs having
g
≤
n.

At first this definition can be difficult to grasp. To insure understanding the reader should prove the following two theorems.

Theorem 26.
X
(
S
_n
)
is the number of colors that is always sufficient and sometimes required to color graphs with g
≤
n.

Theorem 27.
X
(
S
_n
) is the smallest number of colors sufficient to color every graph that can be drawn on
S
_n
without edge-crossings
.

Implicit in the definition of
X
(
S
_n
) is the assumption that it exists; i.e. that for every
n
≥ 0 there
is
a largest
X
for graphs with
g
≤
n.
That this is true is a consequence of the Heawood Coloring Theorem,
which we shall get to shortly. In the meantime it is easy to prove that at least one surface does indeed have a chromatic number.

Theorem 28.
X
(
S
₀
)
is either
4
or
5.

Proof.
The Five Color Theorem asserts the existence of a number of colors—namely 5—which is sufficient to color every graph with
g
= 0. The existence of such a number implies the existence of a smallest number with the same property, so
X
(
S
₀
) exists and in fact
X
(
S
₀
) ≤ 5.

On the other hand
K
₄
has
g
= 0 and
X
= 4 so
X
(
S
₀
) ≥ 4.

We can use the notion of chromatic number of a surface to restate the Four Color Conjecture very concisely.

The Four Color Conjecture.
X
(
S
₀
) = 4.

Of course, this has never been proved, so the best we can say is that
X
(
S
₀
) is 4 or 5. As
S
₀
is in some sense the “simplest” of the surfaces
S
_n
, and not even
its
chromatic number is known exactly, one would expect no more, and probably less, to be known about
X
(
S
_n
) for
n
> 0. Incredibly, for every
n
> 0, the exact value of
X
(
S
_n
) is known! The theorem that gives these values is called the Heawood Coloring Theorem, but before we can state it there are some necessary preliminaries.

Definition 34.
If × is a number then “ [x]” denotes the greatest integer that is less than or equal to x.

Examples.
[3/16] = 0; [16/3] = 5; [− 7/3] = − 3; [4] = 4.

Do not confuse [x] with {x}. They have the same value if × is an integer, but otherwise [x] is the first integer “before” × whereas {x} is the first integer “after” x.

Lemma 29.
If × and y are numbers and
m
is an integer
,
then

and

Proof.
Let × =
p
+
i
and y =
q
+
j
where
p
and
q
are integers, 0 ≤
i
< 1, and 0 ≤
i
< 1. The details are left to the reader.

Heawood Coloring Theorem.
if n
> 0
then

Proof.
Let “t” denote the integer
. We would have the theorem if we could show that X(
S
_n
) ≤
t
and
X
(
S
_n
) ≥
t.

In 1890 Heawood conjectured the theorem and proved the first inequality. One proves the first inequality by showing that
t
colors are sufficient to color every graph with
g
≤ n; it follows that for each
n
> 0,
X
(
S
_n
) exists and in fact
X
(
S
_n
) ≤
t.
We will not do this, as such a proof would be quite long. The interested reader can find a proof of the first inequality in
Graph Theory
by Harary, pp. 136–137.

The theorem has the hypothesis “
n
> 0” because all known proofs of the first inequality fail for
n
= 0.

The second inequality, which was beyond Heawood's ability, is nowadays quite easy to prove. It follows directly from
Theorem 22
, proved in 1968.

To prove that
X
(
S
_n
) ≥
t
it is sufficient to find a graph with
g
≤
n
and
X
=
t.
It so happens that the complete graph
K
_t
is such a graph. That
K
_t
has
X
=
t
is obvious; we will now verify that it has
g
≤
n.

For every
n
> 0,
t
≥ 3 so
Theorem 22
applies. Thus
K
_t
has genus

(by
Lemma 29
(1))

The Heawood Coloring Theorem is an amazing theorem. It tells us that our intuition is wrong in considering
S
₀
the “simplest” of the surfaces
S
₀
,
S
₁
,
S
₂
, ..., for it is the
only
surface in the family whose chromatic number is not known exactly. Thus from the perspective of coloring at least,
S
₀
is the most “complicated” surface.