Introduction to Graph Theory (38 page)

We have mentioned that the proof of the theorem is valid only for
n
> 0, so we can't substitute
n
= 0 into the formula

If we do it anyway—just to see what happens—the result is

precisely the value claimed by the Four Color Conjecture. Some believers in the Four Color Conjecture derive tremendous psychological support from this. They reason that a “neat” formula like

proved for all positive integers
n
without exception, must certainly be true for
n
= 0 as well, and that someday the proof of the theorem will be extended to cover this case. Other, more cynical, mathematicians point to
Theorem 22
as an example of a “neat” formula that cannot be extended to other cases—see
Exercise 5
—and suggest that the Heawood Coloring Theorem might be similar and the Four Color Conjecture false. Perhaps time will tell
*
. In the meantime the Heawood Coloring Theorem continues to tantalize, insuring a future supply of Four Color addicts.

Exercises

  
1.
  
Make a crossing-free drawing of
K
₆
on
S
₁
and count its faces. Use Euler's Second Formula to verify your count.

  
2.
  
Make a crossing-free drawing of
K
₇
on and
S
₁
count its faces. Use Euler's Second Formula to verify your count.

  
3.
  
Make a crossing-free drawing of
K
₈
on
S
₂
.

  
4.
  
Prove that the graph
H
mentioned in the proof of Euler's Second Formula is connected.

  
5.
  
Show that
Theorem 22
is false for
v
= 1 and
v
= 2.

  
6
.
  
Prove that the graph of
Figure 135
has genus 2.

  
7.
  
Make a table showing the values of
v
,
f
,
e
, and
g
for
K
_v
, 1 ≤
v
≤ 20. For what values of
v
does
v
exceed
g
?

  
8.
  
If
G
is a graph with 994 vertices and 492, 753 edges, estimate its genus.

  
9.
  
Prove that a graph for which
L
=
U
is a complete graph. “
L
” and “
U
” are defined on pages 156—157.

10.
  
Prove that for any integer
g
> 1,
P
(3, 7) is larger than
P
(7, 3),
P
(5, 4),
P
(4, 5), and
P
(4, 6). “
P
(
d
,
n
)” is defined on page 158.

11.
  
The graph of
Figure 126a
is nonplanar, so its genus is at least 1. Prove that its genus is exactly 1 by drawing it on
S
₁
without edge-crossings. Then do the same for the graph of
Figure 126b
.

12.
  
Prove that the graph of
Figure 143
has genus 3.

13
.
  
Find
f
for the first two graphs in
Figure 126
, and for the graph in
Figure 143
.

14.
  
If a graph has 18 edges and 7 vertices, what is its genus? If a graph has 52 edges and 11 vertices, what is its genus?

15
.
  
Prove: if a graph is connected of genus
g
and the boundary of every face is
K
₃
then
e
= 3(
v
− 2 + 2
g
).

16.
  
Prove that the graph
L
of
Figure 140
is 1-platonic with
d
= 3 and
n
= 6.

17.
  
Prove that
K
₇
is 1-platonic with
d
= 6 and
n
= 3.

18.
  
The 1-platonic graph
Q
of
Figure 141
is the skeleton of a “toroidal polyhedron”, i.e. a polyhedron which, if inflated, would look like
S
₁
. The toroidal polyhedron has been drawn in
Figure 144
; it looks like a cube through which a square hole has been bored, causing the top and bottom of the cube to collapse a bit around the hole.
K
₇
is also the skeleton of a toroidal polyhedron, called the “Császár polyhedron”; read Martin Gardner's article about the Császár polyhedron in the May, 1975 issue of
Scientific American
and use his pattern to make a cardboard model of it.

Figure 143

Figure 144

19.
  
Is the 1-platonic graph
L
of
Figure 140
also the skeleton of a toroidal polyhedron? If so draw it or make a cardboard model; otherwise explain why not.

20
.
  
There are infinitely many 1-platonic graphs. Prove this by describing, and drawing the first few members of, an infinite family of 1-platonic graphs having
d
= 4 and
n
= 4.

21
.
  
A graph has
v
= 12 and
X
= 10. Prove that its genus is no less than 4 and no more than 6.

22.
  
Definition.
The minimum number of edge-crossings with which a graph can be drawn in a plane is called the
crossing number
of the graph, denoted “
k
”.

Examples.
Every planar graph has
k
= 0.
K
₅
and
UG
have
k
= 1.
K
₆
has
k
= 3; it has been drawn with only three edge-crossings in
Figure 130a
.

Prove that for every graph
g
≤
k.

23.
  
The graph of
Figure 104b
has
k
= 4. Draw it in a plane with only four edge-crossings. Then prove it has
g
= 1.

24.
  
Find the genus and crossing number of the Petersen graph (
Figure 88
, page 93).

25
.
  
In the course of drawing
K
_v
, where
v
≥ 3, what is the maximum number of edges that can be drawn without an edge-crossing? (For
K
₅
the answer is 9; for
K
₆
it is 12.) Though this question can be answered with a simple formula (once you find it, by the way, don't forget to prove that it's correct), no one has yet found a formula for the crossing number
k
of
K
_v
. This is because there doesn't seem to be any way of predicting how many crossings will be caused when the remaining edges are drawn; for example
K
₁₀
has 45 edges, 24 of which can be drawn without edge-crossings, but the remaining 21 edges cause
k
= 60 crossings.

26.
  
Prove the following analog of
Corollary 13
(page 108): if a graph has
g
= 1, then it has at least one vertex with degree ≤ 6.

Suggested reading

On K
₇
and the Császár Polyhedron

“Mathematical Games” department by Martin Gardner in the May, 1975 issue of
Scientific American.

On Crossing Numbers

“Mathematical Games” department by Martin Gardner in the June, 1973 issue of
Scientific American.

*
It has. See Afterword, p. 195.

8. EULER WALKS AND HAMILTON WALKS

Introduction

In this chapter we will examine two of the oldest problems in graph theory: “When does a graph have an Euler walk?” and “When does a graph have a Hamilton walk?” Apart from the age of the problems discussed, there is another respect in which this chapter is different from previous chapters. In
Chapters 3–7
we were concerned almost exclusively with graphical properties that are defined in terms of the surfaces on which the graphs can be drawn. In this chapter, on the other hand, we will examine graphical properties that are unrelated to the surfaces on which the graphs can be drawn.

Euler walks

Definition 35
.
A walk
A
₁
A
₂
...
A
_n
−1
A
_n
in a graph is
closed
if
A
₁
and
A
_n
are the same vertex; otherwise the walk is
open
.