Introduction to Graph Theory (33 page)

Figure 134

Figure 135. A graph of genus 2

Our assumption is that a similar phenomenon
occurs for any connected graph.

Assumption
. If
G
is a connected graph of genus
g
then there exists a crossing-free drawing of
G
on
S
_g
such that through each of the
g
holes of
S
_g
there is a ring composed of vertices and edges of
G
.

This assumption is reasonable. If
G
has genus
g
then
G
cannot be drawn without edge-crossings on any of the surfaces
S
₀
,
S
₁
, ...,
S
_{g
− 1}
having fewer than
g
holes, so each of the
g
holes is somehow crucial to making a crossing-free drawing of
G
. Thus at least one edge of
G
must pass through each hole, which edge can be joined with others to make a ring through that hole.

Figure 136. Crossing-free drawing of
G
on
S
₂
(view is from the top; vertex 5 and dotted edges are underneath; edges 12, 13, 23, 67, 68, and 78 drawn along rim)

Figure 137. Last drawing rearranged to show rings 2372 and 4584 (vertex 5 and dotted edges are underneath; edges 13, 67, 68, and 78 drawn along rim)

We are now ready to prove Euler's
Second Formula. The proof has been illustrated in
Figure 138
for a graph of genus 4. Only the rings have been drawn for the sake of simplicity. You will have to imagine the rings as being but a portion of a much larger network of vertices and edges on the surface
S
₄
.

Figure 138

Euler's Second Formula.
If G
is connected then
v
+
f
−
e
= 2 −
g

Proof.
Let
G
be a connected graph of genus g. Then by our assumption there exists a crossing-free drawing of
G
on
S
_g
such that through each hole there is a ring composed of vertices and edges of
G
. Take a pair of imaginary scissors and cut carefully along each ring, splitting each vertex and edge of the ring into two vertices and two edges. The result is that each of the original rings has been replaced by two new rings, each of which forms the rim of an open-ended tube. See
Figure 138b
. Since there were originally
g
rings there are 2
g
of these rims. Cover these rims with disc-shaped surfaces. The resulting surface, together with its network of vertices and edges, can be inflated and then continuously deformed into
S
₀
. See
Figure 139
. The final result is a new graph
H
drawn on
S
₀
. It is clear from the foregoing that the drawing of
H
on
S
₀
is crossing-free; it is also true that
H
is connected—see
Exercise 4
. Thus
H
is both planar and connected, Euler's First Formula applies, and we have
v
_H
+
f
_H
−
e
_H
= 2. All that remains is to relate the numbers of vertices, faces, and edges of
H
on
S
₀
to those of
G
on
S
_g
.

Figure 139

Let
x
=
v
_H
−
v
_G
. All new vertices were created when we cut the original rings in two lengthwise. Since rings are cyclic graphs and
have as many vertices as edges, it follows that
x
=
e
_H
− e
_G
. Finally, since the only new faces were created when we covered the 2
g
rims, we have
f
_H
=
f
_G
+ 2
g
. Thus

and the theorem is proved.

Some consequences

Lemma 21
. If a connected graph
G
has
v
≥ 3
and genus
g
then
3
f
≤ 2
e
.

Proof.
Imitate the first part of the proof of
Theorem 11
. I leave the details to you.

Theorem 21
. If
G is connected with v
≥ 3
and genus
g
then

Proof.
By the lemma we know 3
f
≤ 2
e
. Since
G
is connected Euler's Second Formula applies and we have
v
+
f
−
e
= 2 − 2
g
. This can be rewritten
f
= −
v
+
e
+ 2 − 2
g
, which upon multiplication by 3 yields 3
f
= − 3
v
+ 3
e
+ 6 − 6
g
. Combining this last with the inequality we get − 3
v
+ 3
e
+ 6 − 6
g
≤ 2
e
, which can be rewritten

Multiplication by − 1/6 gives the theorem.

Using this theorem we can find a lower bound for the genus of a connected graph, even if we know nothing more than its number of vertices and number of edges.

Example.
Let
G
be a connected graph with 52 vertices and 201 edges. Then by the theorem
g
≥ (1/6)201 − (1/2)50 = 33½ − 25 = 8½. But
g
is an integer so we can conclude that the genus of
G
is at least 9.

The next theorem can be used to find an upper bound for the genus of a graph. The theorem was first stated as a conjecture by P. J. Heawood in 1890, but its proof was not completed until 1968. The proof is in two parts and we will do only the easier part. First, two lemmas and a definition. The easy proofs of the lemmas are left to you.

Lemma 22.
If a graph
H
of genus
g
_H
can be drawn on
S
_n
without edge-crossings
, then
g
_H
≤
n
.