Introduction to Graph Theory (28 page)

Figure 114

Suggested reading

On the Regular Polyhedra

*“The Five Platonic Solids” by Martin Gardner, reprinted as Chapter 1 of
The Second Scientific American Book of Mathematical Puzzles and Diversions
by Martin Gardner (Simon and Schuster, 1961).

*100 Great Problems of Elementary Mathematics, Their History and Solution
by Heinrich Dorrie (Dover, 1965), Problem 71. Dorrie proves that there are only five regular polyhedra using spherical geometry.

On Johannes Kepler

*The Watershed
by Arthur Koestler (Doubleday Anchor, 1960). Chapter 2, “The Perfect Solids,” is an account of Kepler's attempt to apply the regular polyhedra to the problem of planetary orbits.

*
Kepler
by Max Caspar (Collier Books, 1962).

6. COLORING

Chromatic number

Having seen what happens when we pile a great many conditions on the graphs under discussion, we will now abandon the escalation of conditions and return to plain old graphs. Despite the title, crayons will not be required for this chapter.

Definition 27
. A graph has been
colored
if a color has been assigned to each vertex in such a way that adjacent vertices have different colors.

In other words, a graph has been colored if each edge has two differently colored endpoints.

Examples
.
1)
Figure 115
shows two colorings of the cube.

Figure 115

2) More often colors are denoted by numbers. An unlabeled graph that has been colored looks a lot like a labeled graph, but the context should prevent any confusion. The graphs in
Figure 116
have been colored; to verify this all you have to do is notice that vertices with the same color are never adjacent.

Definition 28
.
The
chromatic number
of a graph is the smallest number of colors with which it can be colored. We shall denote the chromatic number of a graph by “
X
”.

It must seem strange to use the letter “
X
”, but we've already used “c” (
Exercise 11
, Chapter 4) and I think of “
X
” as being the Greek letter chi (χ).

Examples
.
1) The cube has
X
= 2. Obviously it requires at least two colors, and
Figure 115b
shows that two are enough.

2) Graph a) in
Figure 116
has
X
= 3. It needs at least three colors because it is a supergraph of
K
₃
and
K
₃
needs three. That three colors are sufficient to color graph a) can be seen from
Figure 117
.

Figure 116

3) Similarly graph b) of
Figure 116
needs at least three colors because it is a supergraph of
K
₃
. As it is obvious from the figure that three colors suffice, graph b) has
X
= 3.

4) It is natural to assume that nonplanar graphs have bigger chromatic numbers than planar graphs. In the broad sense, this is true; that is, if a nonplanar graph and a planar graph are chosen at random, it is likely that the nonplanar graph will have the larger chromatic number. However, there are infinitely many exceptions. For example, the thoroughly nonplanar graph of
Figure 118a
has
X
= 2, while the simple planar graph of
118b
has
X
= 4.

Figure 117

Figure 118

A graph can always be colored by giving a different color to every vertex, so for any graph
X
≤
v
. And of course
X
is always at least 1, so the chromatic number of a graph must satisfy the inequality 1 ≤
X
≤
v
. The complete graphs are the only graphs for which
X
is actually equal to
v,
as any other graph has at least one pair of nonadjacent vertices, which can be given the same color; and the null graphs are the only graphs with
X
= 1, as any other graph has at least one edge, which must have its endpoints differently colored. With these exceptions therefore, the chromatic number of a graph must satisfy the inequality 2 ≤
X
≤
v
− 1.

For an arbitrary graph there is no simple rule for determining where within the range 2 ≤
X
≤
v
− 1 the chromatic number falls. In most cases the thing to do is color the graph as economically as you can and then study the result until you are certain that no coloring is possible with fewer colors. For a complicated graph it may be necessary to write down a proof that it cannot be colored with fewer colors.

Coloring planar graphs

It is a simple matter to find planar graphs with
X
= 1, 2, 3, or 4. For example
N
₇
, the cube, graph b) of
Figure 116
, and
K
₄
are planar graphs that have respectively those chromatic numbers. But no one has ever found a planar graph with
X
larger than 4; so it appears that planar graphs always have
X
≤ 4. No one has succeeded in proving this, though the prevailing mathematical opinion is that it is true. A statement that mathematicians can prove is called a “theorem”, or sometimes a “lemma” or “corollary” if it bears a certain relationship to another theorem. A statement that mathematicians believe but cannot as yet prove is called a “conjecture”. A conjecture is an unsolved problem. The task is to either prove that the conjecture is true, at which point the conjecture is promoted to “theorem”, or show by example that the conjecture is false. If either thing happens the conjecture has been “resolved”. A few sentences ago we made a conjecture about the chromatic number of a planar graph. Let us now state this conjecture formally, with its traditional name.

The Four Color Conjecture
.
Every planar graph has X
≤ 4.

Because of its accessibility—the conjecture can be explained to anyone in a couple of minutes—and its persistent failure to be resolved—mathematicians have been trying for more than 120 years— the Four Color Conjecture is one of the most famous unsolved problems in mathematics.

In 1879 a mathematician named A. B. Kempe published a purported proof of the Four Color Conjecture, only to have it shot down ten years later by P. J. Heawood. But Heawood's criticism of Kempe's “proof” was not solely destructive, for he showed how the previous attempt could be modified into a satisfactory proof of what is now called the Five Color Theorem.

The Five Color Theorem
.
Every planar graph has X
≤ 5.

This is a theorem, not a conjecture. It is provable; in fact, we shall prove it shortly. The Five Color Theorem guarantees that there are no planar graphs with
X
> 5. But we are still left with the question, “Are there any planar graphs with
X
= 5?” No one knows. The Four Color Conjecture stands unscathed as a most maddening puzzle.

Periodically mathematical circles are electrified with the rumor that someone has resolved the Four Color Conjecture. But careful examination of the proposed proofs has always disclosed an error. In a way, think, it would be a shame if the conjecture were ever resolved, for the suspense and mystery would evaporate.
*

Like few other mathematical problems, the Four Color Conjecture offers the average nonmathematician a chance at a place in the annals of mathematical achievement. If the conjecture is true, of course, a proof of that fact is probably beyond most people, including most mathematicians; and admittedly the prevailing opinion is that the Four Color Conjecture is true. But if it is in fact false—prevailing mathematical opinion has been wrong before—then all that is required to show this is the discovery of a planar graph with
X
= 5. If such a graph exists and is not monstrous—say, if it has fewer than 100 vertices—then it might be discovered by almost anyone. You might enjoy trying to construct such a graph, sometime between now and the end of your life. Once again, the task is simply to draw a planar graph that requires five colors. Success will bring instant fame. One qualification: in 1969 the Four Color Conjecture was proved for planar graphs with
v
≤ 39, so any planar graph requiring five colors must have at least 40 vertices.

Proof of the Five Color Theorem

The proof of the Five Color Theorem is rather long and involved. In order to comprehend it, you may have to peruse it several times. But I think the investment of brain-strain is worthwhile, for your own intellect is far more compelling than outside authority.

The Five Color Theorem
.
Every planar graph has X
≤ 5.

Proof
. The proof is by mathematical induction on
v
. Let
S
be the statement, “every planar graph with
v
vertices has
X
≤ 5.” Then
S
is a statement about positive integers and we will have the Five Color Theorem if we can prove that
S
is true for every positive integer. By the principle of mathematical induction it will suffice to prove the statements numbered (1) and (2) below. As in most induction proofs, the first is a snap and the second more difficult.