Introduction to Graph Theory (34 page)

Lemma 22a.
If
H
is a supergraph of G, then g
_H
≥
g
_G
.

Definition 31.
If × is a number, then “{x}” denotes the least integer that is greater than or equal to x.

The braces round up to the next whole number, if necessary. If × is an integer then {x} = x; otherwise {x} is the first integer after x.

Examples.
{3/16} = 1; {16/3} = 6; {-7/3} = − 2; {4} = 4.

Though “{x}” also denotes “the set containing x”, context should prevent any confusion.

Theorem 22.
If
v
≥ 3 the
complete graph
K
_v
has genus

Proof.
The idea is to show that

and

which together imply the theorem. The proof of the first inequality is based on
Theorem 21
and is rather short.

Let
v
be a positive integer greater than
or equal to 3. Then
K
_v
is connected with
v
≥ 3, and
e
= (1/2)
v
(
v
− 1) by
Theorem 2
.
Theorem 21
applies and we have

But
g
is an integer so we can say a bit more:

This much Heawood knew. It is the second inequality that is difficult to prove, and whose proof was not completed until 1968. By Lemma the second inequality would be proved if we could draw
K
_v
without edge-crossings on
S
_n
, where

This is exactly what has been done, bit by bit, by various mathematicians since Heawood first conjectured the theorem in 1890. In 1968 the final case was disposed of by G. Ringel and }. W. T. Youngs. Harary recounts the highlights of this 78-year epic in
Graph Theory,
pp. 118–119.

Corollary 22.
If
G has v
≥ 3
and genus
g
then

Proof. G
is a subgraph of
K
_v
and so by
Lemma 22a
,
g
is less than or equal to the genus of
K
_v
.

Corollary 22a.
If
G
is connected with v
≥ 3
and genus
g
then

Proof.
Combine
Corollary 22
,
Theorem 21
,
and the fact that
g
is an integer.

Estimating the genus of a connected graph

If a connected graph has a relatively large number of edges the last corollary can be used to estimate its genus rather closely. By “relatively large number of edges” we mean that
e
is close to its maximum value (1/2)
v
(
v
− 1).

Examples
. In the last section we considered a connected graph
G
with
v
= 52 and
e
= 201. A graph with 52 vertices can have up to (1/2)·52·51 = 1326 edges, so
G
has relatively few edges. The last corollary tells us {(1/6)·201 − (1/2)·50} ≤
g
≤ {49·48/12}, or 9 ≤
g
≤ 196—not a good estimate.

To see how estimates become better as
e
becomes larger let us now consider a connected graph
H
with
v
= 52 and
e
= 1200. 1200 is large relative to the ceiling 1326. This time the lower bound {(1/6)
e
− (1/2)(
v
− 2)} = {(1/6)·1200 − (1/2)·50} = 175, and so 175 ≤
g
≤ 196—a much better approximation.

The best approximation is of course when the upper and lower bounds are the same and
g
is determined exactly. Let us investigate how close
e
would have to be to (1/2)
v
(
v
− 1) for this to happen.

Let “L” denote

and “
U
” denote

If {
L
} = {
U
} then either
L
=
U
or 0 <
U
−
L
< 1. A graph for which
L
=
U
is a complete graph—see
Exercise 9
—and its genus is known by
Theorem 22
, so we are uninterested in this case. Suppose then that 0 <
U
−
L
< 1. Unfortunately, it does not follow that {
L
} = {
U
}, for no matter how small
U
−
L
is, there is always the possibility that there is an integer between
L
and
U,
in which case {
L
} is that integer but {
U
} is the next integer. But at least we can say this: if 0 <
U
−
L
< 1 then either {
L
} = {
U
} − 1 or {
L
} = {
U
}. Let us therefore rearrange the inequality 0 <
U
−
L
< 1 and see what restriction it places on
e
.