Introduction to Graph Theory (26 page)

16.
  
Prove: if
G
is planar and connected with 3 and the boundary of every face is
C
₄
, then
G
is polygonal and
e
= 2
v
− 4
.

17.
  
Prove: if the connectivity
c
of a graph is at least 6, then the graph is nonplanar
.

18.
  
Prove: if a nonplanar graph has
v
≥ 6,
c
≥ 3, and a subgraph which is an expansion of
K
₅
, then it also has a subgraph which is an expansion of
UG
. This is what I had in mind on page 86 when I advised you that “the vast majority of nonplanar graphs contain an expansion of
UG
, so start by looking for that.”

Suggested reading

On Leonhard Euler

*Men of Mathematics
by Eric Temple Bell (Simon and Schuster, paperback edition 1962), chapter 9.

On Topology

What is Mathematics?
by Richard Courant and Herbert
Robbins (Oxford University Press, 1941), chapter V. One of the best all-around mathematics textbooks since Euclid. Chapter V has been excerpted in volume 1 of
*The World of Mathematics,
edited by James R. Newman (Simon and Schuster, 1956).

Intuitive Concepts in Elementary Topology
by B. H. Arnold (Prentice-Hall, 1962).

Topology
by E. M. Patterson (Interscience Publishers, 1959).

*“Topology” by Albert W. Tucker and Herbert S. Bailey, Jr. in the January, 1950 issue of
Scientific American;
reprinted as chapter 19 of
Mathematics in the Modern World: Readings from Scientific American
with introductions by Morris Kline (W. H. Freeman, 1968).

5. PLATONIC GRAPHS

Introduction

Platonic graphs are fun to talk about for three reasons. The first is historical: the five most interesting platonic graphs are identifiable with the five so-called “platonic solids” (after Plato) of ancient mathematics and mysticism. The second is heuristic: the theory of platonic graphs is a spectacular warning to mathematicians of what can happen if they overindulge their natural tendency to place conditions on the objects they are studying. And the third is pedagogical: the theorem proved in this chapter is a striking demonstration of the power of Euler's Formula.

Definition 25
. A graph is
regular
if all the vertices have the same degree. If the common value of the degrees of a regular graph is the number
d
, we say that the graph is
regular of degree d
.

Examples
. 1) Any cyclic graph
C
_v
is regular of degree 2.

2) Any complete graph
K
_v
is regular of degree
v
− 1.

3) Any null graph
N
_v
is regular of degree 0.

4)
UG
is regular of degree 3.

5)
Figure 108a
is regular of degree 3.

6)
Figure 108b
is regular of degree 4.

Figure 108

Definition 26
.
A graph is
platonic
if it is polygonal, regular, and has the additional property that all of its faces are bounded by the same number of edges.

Examples
.
Let us search among the previous examples for platonic graphs.

1) Each
C
_v
is platonic. It is polygonal and regular, and each of its two faces is bounded by
v
edges.

2) Of the complete graphs only
K
₁
,
K
₃
, and
K
₄
are polygonal. All three are regular.
K
₁
has only one face, that bounded by 0 edges, so
K
₁
is platonic, though shallowly.
K
₃
is the same as
C
₃
and is platonic. Each of the four faces of
K
₄
is bounded by 3 edges, so
K
₄
is platonic as well.

3)
N
₁
is the only polygonal null graph. It is the same as
K
₁
and so is platonic.

4)
UG
is not polygonal, so it is not platonic.

5)
Figure 108a
is not polygonal because the central edge borders only the infinite face. Even if it were polygonal it would still not be platonic because it has faces bounded by 3, 4, and 9 edges.

6)
Figure 108b
is a supergraph of
UG
. Hence it is nonplanar, hence it is not polygonal, hence it is not platonic.

There has been a steady escalation of conditions since our first discussions in
Chapter 2
. Then we talked about plain old graphs. Subsequently we restricted our attention to planar graphs, then to planar connected graphs, then to planar connected graphs with each edge bordering two faces (polygonal graphs), and now to planar connected regular graphs with each edge bordering two faces and all faces bounded by the same number of edges (platonic graphs). Whew! Every time a new condition is added we find ourselves talking about fewer things than before. This process of piling condition on condition can lead to ridiculous results. The term “platonic” is a case in point, as there are very few platonic graphs. In fact, other than the ones we have already discovered—
K
₁
,
K
₄
, and the cyclic graphs
C
_v
—there are only four! We now turn our attention to proving this remarkable fact.

Proof of the theorem

Lemma 14
. If
G
is regular of degree
d
then
e
= dv/
2.

Proof
. Left to the reader. A “lemma” is an auxiliary theorem used to prove another theorem.

Lemma 15
.
If
G
is a platonic graph,
d
is the degree of each vertex, and n is the number of edges bounding each face, then
f
= dv/n
.

Proof
. Left to the reader.

Theorem 16
.
Other than
K
₁
and the cyclic graphs there are only five platonic graphs
.

Proof
. Let
G
be a platonic graph which is not
K
₁
or a cyclic graph. Let
d
be the degree of each vertex of
G
and let
n
be the number of edges bounding each face.

If
d
were 0,
G
would be a platonic null graph, i.e.,
K
₁
. But
G
is not
K
₁
so
d
≠ 0.

If
d
were 1, then
G
would not be polygonal—see
Exercise 1
. But
G
is polygonal so
d
≠ 1.

If
d
were 2, then
G
would be a cyclic graph—see
Exercise 2
. But
G
is not cyclic so
d
≠ 2.

Thus we conclude that
d
≥ 3. Note that
n
, being the number of edges bounding a face of a polygonal graph, is also at least 3.

The proof is now half over. The remaining half consists in substituting the formulae of the two lemmas into Euler's Formula, performing a few algebraic manipulations, and interpreting the result.

G
is planar and connected so
v
+
f
−
e
= 2. By the lemmas,
e
=
dv
/2 and
f
=
dv/n
. Thus

Multiplying both sides by 2
n
we get

v
and 4
n
are both positive numbers so (2
n
+ 2
d
−
nd
) must be positive also; that is,

The last inequality is the punch line. It was deduced from the premise that we were dealing with a platonic graph other than or a cyclic graph, hence the “
d
” and “
n
” of
every
platonic graph, other than
K
₁
or a cyclic graph, must satisfy (
n
− 2)(
d
− 2) < 4. But (
n
− 2)(
d
− 2) < 4 has only five solutions for which
d
≥ 3 and
n
≥ 3, and to each of these there corresponds but one platonic graph.

The table on p. 121 was constructed as follows. The first two columns contain all possible combinations of
d
and
n
that satisfy (
n
− 2)(
d
− 2) < 4 together with our earlier discoveries that
d
≥ 3 and
n
≥ 3. A little reflection will show that there are no more possibilities. Think about this until you are convinced.

Then, knowing particular values for
d
and
n, v
can be computed from
equation (1)
, which can be rewritten

Thus the third column.
Lemma 14
tells you how to compute
e
from
d
and
v
, and this was done to produce the fourth column. Finally, the values of
f
in the fifth column were computed from the values of
d, v
, and
n
using
Lemma 15
. To each row of the table there corresponds one and only one platonic graph, whose traditional name is given in the last column. These graphs have been drawn in
Figure 109
; we will explain their names in the next section.