Introduction to Graph Theory (36 page)

If we combine inequalities (1) and (4) the lemma is proved.

In
Chapter 5
we discovered that there are infinitely
many 0-platonic graphs, all' but five of which are either trivial (
K
₁
) or uninteresting (the cyclic graphs). The next theorem says that if
g
> 1 there are at most a finite number of
g
-platonic graphs. “At most a finite number” means that there are either none at all or, if some exist, that they are finite in number.

What can be easily proved about 1-platonic graphs is less spectacular and is contained in a subsequent theorem.

Theorem 24.
For each g
> 1
there are at most a finite number of
g
-platonic graphs
.

Proof.
Pick an integer
g
> 1. If for the
g
selected there are no
g
-platonic graphs then the theorem is true, so we may as well assume that
g
-platonic graphs do exist.

Let
G
be a
g
-platonic graph. Then
e
=
dv
/2,
f
=
dv
/
n
—both by
Lemma 24
—and
v
+
f
−
e
= 2 − 2
g
by Euler's Second Formula. Thus

v
is a positive so
P
(
d
,
n
) is positive and (
n
− 2)(
d
− 2) > 4 by
Lemma 24b
. We also know that
d
≥ 3 and
n
≥ 3 by
Lemma 24a
.

Case 1: n
= 3.

Then (3 − 2)(d − 2) > 4 implies that
d
≥ 7, so by
Lemma 24c
v
=
P
(
d
,
n
) ≤
P
(7, 3).

Case 2: n
= 4.

Then (4 − 2)(
d
− 2) > 4 implies that
d
≥ 5, so by
Lemma 24c
v
=
P
(
d
,
n
) ≤
P
(5, 4).

Case 3: n
= 5.

Then (5 − 2)(
d
− 2) > 4 implies that
d
≥ 4, so by
Lemma 24c
v
=
P
(
d
,
n
) ≤
P
(4, 5).

Case 4;
n
= 6.

Then (6 − 2)(
d
− 2) > 4 implies that
d
≥ 4, so by
Lemma 24c
v
=
P
(
d
,
n
) ≤
P
(4, 6).

Case 5: n
≥ 7.

Then any
d
≥ 3 is admissible and
v
=
P
(
d
,
n
) ≤
P
(3, 7) by
Lemma 24c
.

It so happens that
P
(3, 7) is the largest
number among
P
(7, 3),
P
(5, 4),
P
(4, 5),
P
(4, 6), and
P
(3, 7) regardless of what number
g
> 1 was chosen at the beginning of the proof—see
Exercise 10
. Thus in all cases
v
≤ P(3, 7).

Our assumption that we were dealing with a
g
-platonic graph
G
has led to the conclusion that
G
has at most
P
(3, 7) vertices. As for each value of
g
> 1 there are only a finite number of graphs with at most
P
(3, 7) vertices, it follows that for each value of
g
> 1 there are at most a finite number of
g
-platonic graphs.

Examples.
1) Let
g
= 2. Then

and all 2-platonic graphs can be found among the graphs with
v
≤ 28.

2) Let
g
= 3. Then

and all 3-platonic graphs can be found among the graphs with
v
≤ 56.

3) Let
g
= 100. Then

and all 100-platonic graphs can be found among the graphs with
v
≤ 2772.

Theorem 25.
All
1-
platonic graphs have either d
= 3 and
n
= 6, or
d
= 4 and
n
= 4, or
d
= 6 and
n
= 3.

Proof.
Let
G
be a 1-platonic graph. Such
things do exist—see the examples below. As above we know that
d
≥ 3,
n
≥ 3,
e
=
dv
/2,
f
=
dv
/
n,
and
v
+
f
−
e
= 2 − 2
g
, so

Being the number of vertices of a graph,
v
≥ 1, hence

There are only three combinations of
d
≥ 3 and
n
≥ 3 that satisfy this last equation, and they are the three mentioned in the theorem.

Examples.
There exist 1-platonic graphs having each of the three possible combinations. The graph
L
of
Figure 140
is 1-platonic with
d
= 3 and
n
= 6—see
Exercise 16
. The complete graph
K
₇
is 1-platonic with = 6 and
n
= 3—see
Exercise 17
. And the graph
Q
of
Figure 141a
is 1-platonic with
d
=
n
= 4, which we shall now verify.

It is apparent from the drawing that
Q
is connected and regular of degree 4. We shall show that
Q
is 1-platonic by showing that it satisfies the other conditions as well.

First, observe that
Q
is nonplanar because it is a supergraph of an expansion of
UG
—see
Figure 141b
and
c
). Therefore
Q
has
g
≥ 1. But
Q
has been drawn on
S
₁
without edge-crossings in
Figure 142
, so the genus of
Q
is exactly 1.

All that remains is to verify that each edge of
Q
borders two faces and that every face of
Q
is bounded by 4 edges. This can be done by studying
Figure 142
. Thus
Q
is 1-platonic with
d
=
n
= 4.

Figure 140. A 1-platonic graph with
d
= 3 and
n
= 6