Introduction to Graph Theory (43 page)

Example
.
The graph of
Figure 159a
is the trisection graph
T
(
G
) of the graph
G
of
Figure 158a
.
Figure 159b
shows the line graph
L
(
T
(
G
)) of
T
(
G
).

Exercises 14
and
16
establish a partial relationship between euler walks and hamilton walks. The following theorem gives a more profound relationship.

Theorem
.
A graph
G
with e
≠ 0
does or doesn't have a closed euler walk according as L
(
T
(
G
))
does or doesn't have
,
respectively
,
a closed hamilton walk
.

Figure 159

Draw some graphs
G
with closed euler walks and in each case check that
L
(
T
(
G
)) has a closed hamilton walk. Then draw a few graphs
G
without closed euler walks and in each case check that
L
(
T
(
G
)) doesn't have a closed hamilton walk. With these examples under your belt try to prove the theorem.

19.
  
It is usually true that different (i.e., nonisomorphic) connected graphs have different line graphs. In fact there is only one exception: there are two different connected graphs having line graph
K
₃
. Find them.

20
.
  
Let
G
be a graph with
v
vertices and
e
edges, and let the degrees of the vertices of
G
be “
d
₁
”, “
d
₂
”,...., and “
d
_v
”. Of course
L
(
G
) has
e
vertices. Prove now that the number of edges of
L
(
G
) is equal to (1/2)(
d
²
₁
+
d
²
₂
+ ... +
d
²
_v
) −
e
.

21.
  
Prove: cyclic graphs are isomorphic to their line graphs, and are the only graphs having that property.

Suggested reading

On Euler Walks and Hamilton Walks

*“The Seven Bridges of Königsberg” by Leonhard Euler, reprinted in volume 1 of
The World of Mathematics
, edited by James R. Newman (Simon and Schuster, 1956).

Mathematics
:
the Man
-
Made Universe
by Sherman K. Stein (W. H.Freeman, 1963), chapter 8.

*
The Enjoyment of Mathematics: Selections from Mathematics for the Amateur
by Hans Rademacher and Otto Toeplitz (Princeton University Press, 1957), chapter 2.

On William Rowan Hamilton

*
Men of Mathematics
by Eric Temple Bell (Simon and Schuster, 1962), chapter 19.

*“William Rowan Hamilton” by Sir Edmund Whittaker in the May, 1954 issue of
Scientific American
, reprinted as chapter 7 of
Mathematics in the Modern World: Readings from Scientific American
with introductions by Morris Kline (W. H. Freeman, 1968).

On the Origins of Graph Theory

Graph Theory
by Frank Harary (Addison-Wesley, 1969), chapter 1.

AFTERWORD

As
Dots and Lines
went to press in 1976, yet another “the Four Color Conjecture has been resolved” rumor was circulating. Only this time the rumor was confirmed.

Toiling in an arcane area that totally baffles most ordinary mortals, mathematicians usually despair of even trying to explain their work to laymen. Yet recently two University of Illinois mathematicians announced a breakthrough of such widespread interest that even the reticent American Mathematical Society issued a rare press release. The news: after more than a century of futile brain racking, one of mathematics' most famous teasers—the so-called four-color conjecture—has finally been proved.

—“Eureka!”,
Time
, Sept. 20, 1976, pp. 87–88

The mathematicians were Kenneth Appel and Wolfgang Haken. The proof is described in two articles in the September, 1977 issue of
Illinois Journal of Mathematics
. Appel and Haken have also written a less technical account for laymen in the October, 1977 issue of
Scientific American
. To make this article more accessible to readers of
Dots and Lines
I would like to recast our proof of the Five Color Theorem (pp. 131–35). Though equivalent logically to the original induction proof, this new proof is rather different psychologically.

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

Proof.
The proof is indirect. We shall suppose that there are some planar graphs with
X
> 5, and show that this assumption leads to a contradiction.

From among the planar graphs with
X
> 5 that we are supposing to exist, choose one—call it
G
—having the minimum number of vertices that such graphs ever have. That is, choose a planar graph
G
so that (1)
G
has
X
> 5 and (2) every planar graph with fewer vertices has
X
≤ 5. I want to establish two statements about
G
, the first of which is

I. None of the graphs in
Figure 160
can be a subgraph of
G
. This is because, if any of the six graphs were a subgraph of
G
, then
G
−
A
(the subgraph of
G
obtained by erasing vertex
A
and all edges incident to vertex
A)
would have
X
≤ 5 (by (2) above) and so
G
would also have
X
≤ 5 (by Cases 1, 2, and 3 on pp. 132–35). But
G
has
X
> 5, so none of the graphs in
Figure 160
can be a subgraph of
G
.

Figure 160

To follow the argument of the preceding paragraph you will have to reread, at the point at which they are mentioned, Cases 1, 2, and 3 of the original proof. To avoid confusion do not read any other parts of the original proof. Begin with the words “Case 1” on p. 132 and stop above the
figure on p. 135
.

The second statement I want to establish about
G
is

II. At least one of the graphs in
Figure 160
must be a subgraph of
G
.

This is by
Corollary 13
(p. 108).

We are in quite a bind. By Statement I
none
of the graphs in
Figure 160
can be a subgraph of
G
, yet by Statement II one of them
must
be. The only way out is to conclude that we were wrong at the outset in supposing that there exist planar graphs with
X
> 5. Thus every planar graph has
X
≤ 5.

In the terminology of Appel and Haken, Statement I says that each of the graphs—they would say “the configurations”—in
Figure 160
is “reducible”. The word “reducible”, which they use for historical reasons only and is not subject to common-sense interpretation, means
roughly “cannot occur as a subgraph of the graph under consideration”.

Continuing in their terminology, Statement II says that the set of configurations in
Figure 160
is “unavoidable”, since the group cannot as a whole be avoided by (i.e., at least one must be a subgraph of) the graph under consideration.

Using these terms we can summarize our new proof of the Five Color Theorem as follows: We have shown that
Figure 160
is an unavoidable set of reducible configurations for a planar graph
G
having
X >
5 and minimal vertices. Finding this set means that no such graph exists, thus there can be no planar graphs with
X
> 5 at all, thus every planar graph has
X
≤ 5.

The Appel-Haken proof of what we should now call the Four Color Theorem has the same organization. To show that every planar graph has
X
≤ 4, they suppose that planar graphs exist with
X =
5 (i.e.
X
> 4, in view of the Five Color Theorem), and focus their attention on one (a “minimal five-chromatic” planar graph) having the minimum number of vertices that such graphs ever have. They then produce an unavoidable set of 1482 reducible configurations for this hypothetical graph, concluding that no minimal five-chromatic planar graph exists, hence no five-chromatic planar graphs exist and every planar graph has
X
≤ 4.

Appel and Haken begin their
Scientific American
article by considering the Four Color Conjecture in its dual form as a problem about coloring the faces, rather than the vertices, of planar graphs (we did the same in “Coloring Maps”, pp. 136–39). But midway through they convert the conjecture into the form in which we first studied it.

In the same article they remark that though this famous conjecture has finally been resolved, the proof's reception by the mathematical community has been cool.

. . . mathematicians . . . who were not aware of the developments leading to the proof are rather dismayed by the result because the proof made unprecedented use of computers; the computations of the proof make it longer than has traditionally been considered acceptable.

The length of the proof is due to the huge size of the unavoidable set of reducible configurations—1482 configurations, as compared to the handful (
Figure 160
) needed for the Five Color Theorem. Having to consider a large number of cases is aesthetically repugnant to a pure mathematician, and if the proof were only unwieldy in the conventional sense, that alone would account for widespread
disappointment. But we learn from the next sentence that the proof is more than “unwieldy”:

In fact the correctness of the proof cannot be checked without the aid of a computer.

The proof then is an altogether new kind of proof, bristling with philosophical problems. It cannot be completely comprehended by any human being!

—April 1978

SOLUTIONS TO SELECTED EXERCISES

Chapter 2. Graphs

4
.
  
S
is not a set. If
S
were a set, then—having just been described in twenty-five words or less—
S
would be an element of itself, in violation of
Definition 1
.

7
.
  
By
Theorem 2
, the right side of the equation is the number of edges of
K
_v
. We can see that the left side is, also, if we imagine drawing
K
_v
as follows: join vertex 1 to vertices 2 through
v
, creating
v
− 1 edges; then join vertex 2 to vertices 3 through
v
, creating
v
− 2 edges; and so on.

8
.
  
(1/2)
v
(
v
− 1)−
e
.

9
.
  
In either graph, focus on one particular vertex—let's call it “
A
”— whose degree is at least 3. Focus on three specific vertices—we'll call them “
B
,” “
C
,” and “
D
”—that are adjacent to
A
. If any of the edges {
B
,
C
}, {
B
,
D
}, or {
C
,
D
} happens to be present in the graph, the graph contains a subgraph isomorphic to
K
₃
. If none of these edges is present, then they are all in the other graph, forming a subgraph isomorphic to
K
₃
over there.

13
.
  
If
C
_v
and
C
_v
are isomorphic, they have the same number of edges, and so
v
(the number of edges of
C
_v
) is equal to (1/2)
v
(
v
− 1) −
v
(the number of edges of
C
_v
, using the result of
Exercise 8
). Solving this equation yields
v
= 5 as the only possibility