Introduction to Graph Theory (32 page)

Figure 130

Think of the surface consisting of
S
₀
with
n
handles
as made of extremely pliable rubber which we are free to stretch, shrink, or otherwise distort as much as we want, provided we don't tear it or fold it back onto itself. With this understanding we see that the surface consisting of
S
₀
with
n
handles can be “continuously deformed” (in the sense of pp. 108–109) into
S
_n
and the edges and vertices of
G
can be carried along with this continuous deformation.
Figure 131
shows this for
S
₀
with three handles; for the sake of clarity the edges and vertices of
K
₆
have been omitted.

Thus
G
can be drawn on
S
_n
without edge-crossings. Since there is at least one member,
S
_n
of the sequence of surfaces
S
₀
,
S
₁
,
S
₂
... on which
G
can be drawn without edge-crossings, there must be a first such member
S
_g
. Then by definition
g
is the genus of
G
and we have the theorem.

In
Figure 130
three handles are added so
n
= 3 and consequently the genus of
K
₆
is 1, 2, or 3 (it is not 0 as
K
₆
is nonplanar). In fact
K
₆
has
g
= 1 (see
Exercise 1
).

Theorem 20.
If a graph
G
has genus
g
then
G
can be drawn without edge-crossings on every surface
S
_n
for which g
≤
n
.

Proof.
Take a crossing-free drawing of
G
and
S
_g
. Find a region on the surface of
S
_g
which contains no edges or vertices of
G
. The region can be small, no matter. Within this region append to the surface of
S
_g
,
n
−
g
tubular handles, where
n
is any number greater than or equal to g. The resulting surface can be continuously deformed into
S
_n
, with the graph
G
carried along. The result is a drawing of
G
on
S
_n
without edge-crossings.

Figure 131

Thus we see that for a
specific graph
G
, its genus
g
cuts the sequence
S
₀
,
S
₁
,
S
₂
, ... into two pieces. The first part
S
₀
,
S
₁
, ...,
S
_{g
− 1}
is finite and consists of all surfaces in the family on which
G
cannot be drawn without edge-crossings. The second part
S
_g
,
S
_g
+1
, ... is infinite and consists of all surfaces on which
G
can be drawn without edge-crossings.

Before we defined genus, a graph was simply planar or nonplanar. With the notion of genus we can say much more. If a graph is nonplanar we can find its genus and thereby specify the
extent
to which it is nonplanar. For example a graph of genus 125 is much farther from planarity than a graph of genus 4.

Since planar graphs are precisely the graphs with
g
= 0, the second corollary to Kuratowski's Theorem (
Corollary 7a
) can be restated: The set of all graphs with
g
= 0 is equal to the set of all graphs that are not supergraphs of expansions of
UG
or
K
₅
. This suggests that there might be similar theorems to be discovered for graphs of higher genus, i.e. theorems of the form “The set of all graphs with
g
= — is equal to the set of all graphs that are not supergraphs of expansions of —”. So far no such theorems have been discovered. It is known, however, that they exist. Harary reports
(Graph Theory,
p. 117) that in 1968 a mathematician named Vollmerhaus proved that for each genus there are finitely many “forbidden” subgraphs. More precisely Vollmerhaus's result is that for each integer
g
≥ 0 there exist a finite number of graphs
H
₁
,
H
₂
, ...,
H
_r
such that the following statement is true: The set of all graphs with genus
g
is equal to the set of all graphs that are not supergraphs of expansions of
H
₁
or
H
₂
or ... or
H
_r
. In the case that
g
= 0,
r
= 2 and the forbidden subgraphs are
H
₁
≅
UG
and
H
₂
≅
K
₅
. In the other cases (
g
> 0) it is only known that the graphs
H exist,
that they are
finite
in number, and that their number and structure depend on
g
—i.e., in general different
g
's have different
r
's and different
H
's. So we know that characterizations of graphs of higher genus, analogous to Kuratowski's for genus 0, exist. But so far none have been stated explicitly and none will be until someone cracks the structure of the
H
's.

Up to now the term “face” has been defined only for planar graphs. To speak of the “faces" of say,
UG,
would have been to speak nonsense. But with the new family of surfaces it is now possible to define the term “face” for any graph.

Definition 30.
If a
graph
G
of genus
g
has been drawn on the surface of
S
_g
without edge-crossings, then the edges and vertices of
G
divide the surface of
S
_g
into regions called the
faces
of
G
. The number of faces of a graph is denoted “
f
”.

If
g
= 0 this definition reduces to the earlier
Definition 23
. Note that as before this definition assumes two things: that the edges and vertices of
G
do in fact cut the surface of
S
_g
into well-defined regions, and that the number of regions is independent of the specific crossing-free drawing of
G
that is used. Both are true and provable, but we will not demonstrate them.

Examples.
1)
UG
has
f
= 3. The faces have been numbered in
Figure 132a
.

2)
K
₅
has
f
= 5. See
Figure 132b
.

Figure 132

A note on counting the faces of nonplanar graphs. In
Figure 132a
, for example, it seems at first that
UG
has more than three faces. The confusion is partly due to the drawing, which is a two-dimensional representation of a three-dimensional object. We have to visualize the hidden parts of the torus, which can be difficult. A good rule of thumb is: if you can get from one place to another without leaving the surface, crossing an edge, or passing through a vertex, the two places are in the same face. In
Figure 132a
it is possible to travel on the surface from any “3” to any other “3” without crossing an edge or passing through a vertex, thus the four “3”'s must lie in the same face. Similar remarks hold for,
Figure 132b
. The unconvinced reader should acquire an inner tube and some chalk.

Euler's Formula says that for planar connected graphs the expression
v
+
f
−
e
always has the value 2. Now that “face” makes sense for nonplanar graphs as well, we might make the hasty conjecture that the same is true for connected graphs of higher genus. That this is not so can be seen by computing
v
+
f
−
e
for the two connected graphs
UG
and
K
₅
; in each case the value is not 2, but 0. Based on this experiment we might hazard a more sophisticated, though still somewhat daring, conjecture that
v
+
f
−
e
has the same value for connected graphs of the same genus. Incredibly, this is true, and the constant value is related to the genus in a strikingly simple way. The theorem is called Euler's Second Formula and we shall indicate its proof in the next section.

Eulers Second Formula

Euler's Second Formula says
that for every connected graph of genus
g
,
v
+
f
−
e
= 2 − 2
g
. For planar graphs this reduces to the earlier result
v
+
f
−
e
= 2, which shall henceforth be known as Euler's First Formula.

Our proof of Euler's Second Formula will not be complete, as it will be based on an assumption that we shall not prove. What follows are some examples to make you feel that the assumption is at least reasonable.

Figure 133a
is a drawing of
K
₅
on
S
₁
. Notice that the walk BCDB goes around through the hole and back again. In
Figure 133b
the vertices and edges have been rearranged a bit to make a perfect ring out of the walk BCDB.

Figure 133

Figure 134a
is a drawing of
UG
on
S
₁
. Again there is a walk—
XAYBX
—that goes around through the hole and can be deformed into a perfect ring (
Figure 134b
).

The graph of
Figure 135
is a less trivial example, having genus 2—see
Exercise 6
. In
Figure 136
the graph has been drawn without edge-crossings on
S
₂
. Notice that there is a walk 2372 going around through the first hole and another walk 4584 going around through the second hole. In
Figure 137
the edges and vertices have been rearranged to make perfect rings out of these walks.