Introduction to Graph Theory (35 page)

We have just proved the following theorem.

Theorem 23.
If
G
is a connected incomplete graph with v
≥ 3
and e
≥ (1/2)
v
(
v
− 1) − 5,
then the upper and lower hounds for
g
given in the last corollary are either the same integer or consecutive integers
.

Examples.
1) For connected incomplete
graphs with
v
= 52 the condition is that
e
≥ (1/2)·52·51 − 5 = 1321, and it so happens that this is enough to determine
g
in all cases. See the following table.

2) On the other hand, for connected incomplete graphs with
v
= 53 the condition
e
≥ (1/2)·53·52 − 5 = 1373 is never sufficient to determine g. See the next table.

g-Platonic graphs

Thus far we have generalized the notion of planarity, introduced in
Chapter 3
, and have proved a generalization of Euler's First Formula, introduced in
Chapter 4
. In this and the next section we shall generalize the results of
Chapters 5
and
6
.

Definition 32.
A graph is
g
-platonic if it is a connected, regular graph of genus
g
such that every edge borders two faces and every face is bounded by the same number of edges.

Specializing the definition to
g
= 0 we have the notion “0-platonic” which coincides with the notion “platonic” defined in
Chapter 5
.

Notation.
In reference to a
g
-platonic graph, “
d
” denotes the degree of each vertex, “
n
” denotes the number of edges bounding each face, and “
P
(
d
,
n
)” stands for the quotient

Lemma 24.
If
G
is g-platonic
then e
=
dv
/2 and
f
=
dv
/
n
.

Proof.
Left to the reader.

Lemma 24a.
If g
> 0
and
G
is g-platonic then d
≥ 3
and n
≥ 3.

Proof.
Left to the reader.

Lemma 24b.
Let g
> 1.
If
(
n
− 2)(
d
− 2) > 4,
then
P
(
d
,
n
) > 0. Conversely if
P
(
d
,
n
) > 0,
then (n
− 2)(
d
− 2) > 4.

Proof.
Left to the reader.

Lemma 24c.
If g
> 1, (
n
− 2)(
d
− 2) > 4,
d'
≥
d
≥ 3, and
n'
≥
n
≥ 3, then
P
(
d'
,
n'
) ≤
P
(
d
,
n
).

Proof.

P
(
d'
,
n'
) and
P
(
d
,
n'
) are positive fractions by the previous lemma. They have the same numerator,
which is positive since
g
> 1. We have just seen that
P
(
d'
,
n'
) has the larger denominator, so

Now let × =
n'
/
n
, so
n'
=
n
x and we can express
P
(
d
,
n'
) as

Similarly, since

we can express
P
(
d
,
n
) as

So we have only to relate the fractions in
equations (2)
and (
3
). They are both positive fractions by
Lemma 24b
. They have the same numerator, which is positive since
g
> 1. That the first has the larger denominator is a simple consequence of the fact that
n'
≥
n
and so × ≥ 1:

Therefore the fraction in
equation (2)
is less than or equal to the fraction in
equation (3)
and we have