Introduction to Graph Theory (31 page)

8.
  
Color the faces of
Figure 123b
with four colors. Don't forget the infinite face.

Suggested reading

On the Four Color Conjecture

All books listed at the end of chapter 4 under the heading “On Topology”. Also:

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

*“The Island of Five Colors” by Martin Gardner, reprinted in
Fantasia Mathematica
edited by Clifton Fadiman (Simon and Schuster, 1958). Science fiction.

The Four-Color Problem
by Oystein Ore (Academic Press, 1967), the Introduction.

“Thirteen Colorful Variations on Guthrie's Four-Color Conjecture” by Thomas L. Saaty in the January, 1972 issue of
The American Mathematical Monthly
.

*
Alas! See Afterword, p. 195.

7. THE GENUS OF A GRAPH

Introduction

This chapter generalizes
Chapters 3–6
. It is more conceptually
difficult and concisely written than the other chapters in this book, so you may find it heavy going, especially if you read it without outside help. Naturally I hope you stick with it, because I think the material is fascinating and so well worth the effort; but as nothing in
Chapter 7
will be needed in
Chapter 8
, you may want to skip
Chapter 7
and go on to
Chapter 8
. Should you decide to do that, however, in order that you will have at least some idea of what
Chapter 7
is about, recommend that you read the next section carefully and at least skim the remainder of the chapter.

The genus of a graph

The term “planar” comprises two conditions. A graph is planar if 1) it is drawn without edge-crossings and 2) it is drawn in a plane. The concept “genus” includes the first condition but generalizes the second by considering graphs drawn on other surfaces.

Figure 127
depicts the first four members of an infinite family of surfaces. These surfaces are taken to be hollow and of negligible thickness. That is, you should think of
S
₀
as a beachball rather than a baseball, of
S
₁
as a valveless inner-tube rather than a doughnut, etc.
S
₀
is called a sphere,
S
₁
is called a one-hole torus,
S
₂
a two-hole torus,
S
₃
a
three-hole torus,
etc. The names of the surfaces are easy to remember if you think of the subscript as referring to the number of holes. Thus
S
₇₉
, say, is a seventy-nine-hole torus and
S
₀
can be considered a “torus” with no holes.

Figure 127

Definition 29.
The
genus
of a graph, denoted “
g
”, is the subscript of the first surface among the family
S
₀
,
S
₁
,
S
₂
,....., on which the graph can be drawn without edge-crossings.

Implicit in the definition is the assumption that every graph
has
a genus; i.e. given an immensely complicated and wildly nonplanar graph
G,
that a systematic search of the sequence
S
₀
,
S
₁
S
₂
, ... will eventually reveal
some
surfaces on which
G
can be drawn without edge-crossings (then
g
is just the subscript of the first such surface). Soon we will prove that indeed every graph has a genus; but first a theorem and some examples to elucidate this new concept.

Theorem 18.
The set of all planar graphs is equal to the set of all graphs with g
= 0.

Proof.
To prove that two sets are equal we have to
show that each is a subset of the other. Accordingly we have two statements to establish, viz., “Every planar graph has
g
= 0” and “Every graph with
g
= 0 is planar.” I'd like to start by proving the latter.

That is, if a graph can be drawn on
S
₀
without edge-crossings, we have to show that it can also be drawn in a plane without edge-crossings. We do this as follows.

Let
G
be a graph drawn on a sphere without edge-crossings. Select
a point of the sphere which is not a vertex and through which no edges pass, and puncture the sphere at that point. Stretch the hole and gradually flatten the sphere out onto a plane. The result will be
G
on the plane, still without edge-crossings, and surrounded by a circle (the boundary of the hole). Erase the circle and we have
G
drawn in a plane without edge-crossings. This process has been illustrated in
Figure 128
.

The other half of the theorem is

That is, if a graph can be drawn in a plane without edge-crossings, we have to show that it can also be drawn on
S
₀
without edge-crossings. We do this by reversing the above procedure.

Let
G
be a graph drawn in a plane without edge-crossings. Cut out of the plane a circular region containing
G
and bend this circular region first into a hemisphere and finally into a sphere that is missing one point. Supply the point and the result is a drawing of
G
on
S
₀
without edge-crossings. To visualize this you should examine the drawings of
Figure 128
in reverse order.

This theorem shows that the concept “planar” is merely a special case of the more general concept “genus”. Planar graphs are the graphs of genus 0.

Figure 128

The fact that edges can go “around the back” of a
sphere may suggest that edge-crossings can be avoided on spheres when they cannot in a plane, but the theorem demonstrates that this notion is false (see
Figure 128
). There is, however, a difference between a crossing-free drawing of a planar graph on
S
₀
and a crossing-free drawing of the same graph in a plane, and that is that the “infinite face” of the plane drawing loses all individuality in the drawing on
S
₀
. There it becomes as finite in extent as all the other faces. Conversely, whichever face of an
S
₀
-drawing of a planar graph is punctured to produce a plane drawing becomes the “infinite face” of the plane drawing. Of course this alteration in no way affects edge-crossings, and it remains true that planar graphs and graphs of genus 0 are precisely the same things.

Examples.
1)
K
₄
has
g
= 0 because it is planar.

2) Each
C
_v
has
g
= 0 because it is planar.

3)
UG
has
g
= 1 because it is nonplanar and so cannot, by
Theorem 18
, be drawn without edge-crossings on
S
₀
; but it can be so drawn on
S
₁
as
Figure 129a
shows. Thus 1 is the subscript of the first surface in the family
S
₀
,
S
₁
,
S
₂
... on which
UG
can be drawn without edge-crossings.

Figure 129

4)
K
₅
has
g
= 1 for the same reasons as
UG.
See
Figure 129b
.

Theorem 19.
Every graph has a genus.

Proof.
Let
G
be any graph. If
G
is planar it has
g
= 0 by
Theorem 18
, so let us assume that
G
is nonplanar. Take a drawing of
G
in a plane and transfer the drawing to the surface of
S
₀
by the procedure used in part (2) of the proof of
Theorem 18
. Add to
S
₀
enough tubular “handles” to serve as “overpasses”, thereby eliminating the edge-crossings. This has been done in
Figure 130
for the case that
G
is
K
₆
. Let the number of handles be
n
. The number
n
might be quite large but it is finite, as a graph can have only a finite number of edges and hence only a finite number of edge-crossings.