Introduction to Graph Theory (23 page)

Figure 100

As before we shall compare the numbers of vertices, faces, and edges of the two graphs. Clearly the relationships are
v
_G
=
v
_H
−
n
,
f
_G
=
f
_H
−
n
, and
e
_G
=
e
_H
− 2
n
. Hence

which is equal to 2 by the last theorem.

Euler's Formula
.
If
G
is planar and connected
,
then v
+
f
−
e
= 2.

Proof.
Combine the two previous theorems.

Euler's Formula is everything a theorem should be. It has the same simple profundity of Kuratowski's Theorem, and an elegant proof—the proofs of
Theorems 8
and
9
—as well.

Some consequences of Euler's Formula

Theorem 11.
If
G
is planar and connected with v
≥ 3,
then
(3/2)
f
≤
e
≤ 3
v
− 6.

Proof.
Let
G
be planar and connected with three or more vertices.

Case 1. G
has a face bounded by
fewer than three edges.

Then a little reflection will reveal that
G
must be the path graph
P
₃
shown in
Figure 101a
. For
P
₃
,
v
= 3,
f
= 1, and
e
= 2. Hence (3/2)
f
= 3/2,
e
= 2, 3
v
− 6 = 3 and the theorem holds.

Figure 101

Case 2.
Every face of
G
is bounded by three or more edges.

Then numbering the faces of
G
from 1 to
f
we can make the series of statements

Hence 3
f
, the sum of the first column, is less than or equal to the sum of the second column, which we can denote by “D”. In shorthand, 3
f
≤
D
. If
G
were polygonal
D
would be equal to 2
e
because every edge of a polygonal graph borders on exactly two faces and so each edge would have been counted exactly twice in the second column, once for each of the two faces it borders. If
G
were not polygonal
D
would be smaller than 2
e
, because planar-connected-nonpolygonal graphs contain one or more edges that border on only one face, and such edges would have been counted only once in the second column, So if
G
were polygonal we would have
D
= 2
e
, whereas if
G
were not we would have
D
< 2
e
. In either case we can safely say that
D
≤ 2
e
. Combining this with 3
f
≤
D
we have 3
f
≤ 2
e
which yields the first half of the theorem when both sides are divided by 2.

To get the other half take (3/2)
f
≤
e
, which we have just proved, and multiply both sides by 2/3 to get
f
≤ (2/3)
e
. Add
v
−
e
to both sides and the result is
v
+
f
−
e
≤
v
+ (2/3)
e
−
e
.
G
satisfies the hypothesis of Euler's Formula, so
v
+
f
−
e
= 2. Therefore

In this theorem the hypothesis that
v
≥ 3 is unavoidable. There
are only two planar and connected graphs with
v
< 3:
K
₁
(for which
v
= 1,
f
= 1, and
e
= 0) and
K
₂
(for which
v
= 2,
f
= 1, and
e
= 1), and the theorem is false for both of them.

Corollary 11.
K
₅
is nonplanar.

Proof.
This proof is independent of the one we constructed in
chapter 3
, and is a lot shorter. Suppose for the sake of argument that
K
₅
were planar. We know that
K
₅
is connected so by
Theorem 11
K
₅
would have the property
e
≤ 3
v
− 6. But
K
₅
has
e
= 10 and 3
v
− 6 = 9, a contradiction, so
K
₅
is nonplanar.

Comparing the proof of this corollary to our original proof that
K
₅
is nonplanar (
Theorem 4
), we get our first glimmer of the tremendous power of Euler's Formula.

Theorem 12.
If
G
is planar and connected with v
≥ 3 and
G
is not a supergraph of
K
₃
, then 2
f
≤
e
≤ 2
v
− 4.

Proof. Case 1. G
has a face bounded by fewer than four edges.

Then—think about this—
G
must be either
P
₃
or
P
₄
, or
T
₄
shown in
Figure 101
. The theorem holds for all three graphs.

Case 2.
Every face of
G
is bounded by four or more edges.

Then we can make the series of statements

and can conclude as in the proof of the last theorem
that 4
f
≤ 2
e
, which upon division by 2 gives the first half of the theorem. Then

Euler's Formula gives
v
+
f
−
e
= 2, so

which is the second half.

As before the hypothesis that
v
≥ 3 is necessary, for the theorem is false for
K
₁
and
K
₂
.

Corollary 12.
UG is nonplanar.

Proof.
This is similar to the proof of the last corollary. Suppose for the sake of argument that
UG
were planar.
UG
is connected and is not a supergraph of
K
₃
, so by
Theorem 12
it would have to be true that
e
≤ 2
v
− 4. But
e
= 9 and 2
v
− 4 = 8, a contradiction, hence
UG
is nonplanar.

In the next section we'll reflect on what has happened in these last two corollaries, but first two more results.

Theorem 13.
If
G
is planar and connected then
G
has a vertex of degree
≤ 5.

Proof.
Let
G
be planar and connected.

Case 1
.
G
has fewer than three vertices.

Then
G
must be
K
₁
or
K
₂
and the theorem holds.