Introduction to Graph Theory (22 page)

Euler's discovery was similar. Euler's Formula says that for any planar connected graph whatever, no matter how simple or complicated, the number
v
of vertices plus the number
f
of faces minus the number
e
of edges always has the same value, 2. Or, in modern terms, Euler's Formula says that for planar connected graphs
v
+
f
−
e
is constant, and the constant is 2. You might want to pause at this point and draw a few dozen planar connected graphs and see for yourself that this is true.

Euler's Formula is rather startling! No matter
what graph you draw, provided that it is crossing-free and in one piece, there is the basic simplicity of
v
+
f
−
e
= 2.

At the risk of seeming hysterical, we might reflect on how closely Euler's Formula approaches being a fundamental law of nature. Take any situation in which lines cross in a plane—a slice of honeycomb, perhaps, or the paths of gamma-rays on a photographic plate, or a madman's doodle. Count the number of line-crossings and line-ends and call that ‘
v
'. Count the number of segments into which the lines are cut by the crossings and call that “
e
”. Count the number of regions into which the lines divide the plane and let that be “
f
”. Then provided only that the situation is connected, you are guaranteed the underlying order of
v
+
f
−
e
= 2.

Mathematical induction

We shall prove Euler's Formula first for polygonal graphs, and then for planar connected graphs that are not polygonal. All the work is in the first proof. To a mathematician even the first proof is quite simple, employing as it does the familiar (to him/her) technique of “mathematical induction”. This section is dedicated to those who have never seen this method of proof.

Principle of mathematical induction.
Let
S
be a statement about positive integers. If one can prove that

      
(1)
  
S
is true for the positive integer 1, and

      
(2)
  
whenever
S
is true for a positive integer it is true for the next positive integer,

then
S
is true for every positive integer.

The foregoing is called a “principle” because it is not usually proved, but taken as an axiom for the system of positive integers. A little thought impels us to grant the principle. If we know that statements and (2) are both proved, we can combine them to conclude that the statement
S
is true for the positive integer 2; then we can combine this new information with statement (2) and conclude that 5 is true for 3; this in combination with (2) implies that
S
is true for 4; this and (2) imply that
S
is true for 5, etc.

A slightly more picturesque model of the principle runs
as follows. Take a box of infinitely many dominoes and number them with the positive integers. We will assume that the laws of nature are suspended and that you manage to come up with both the paint and time required to do this. Stand the dominoes on end, in order, on a table top (infinite table required here). We will interpret “
S
is true for the positive integer n” as meaning that the domino bearing the number
n
falls over. Then statement (1) of the principle becomes “domino 1 falls over” and statement (2) becomes “whenever a domino falls over the next domino falls over.” Under this interpretation the conclusion of the principle says merely that all the dominoes fall over.

The principle is called “induction” because, though it is in fact a method of deductive reasoning, it somewhat resembles the examina-tion-of-cases characteristic of inductive reasoning. If an argument by “mathematical induction” were really inductive, it would have no validity in mathematics.

Proof of Euler's Formula

Theorem 8
. If
G
is polygonal then
v
+
f
−
e
= 2.

Proof
. The proof is by induction on
f
. Let
S
be the statement, “
v
+
f
—
e
= 2 holds for all polygonal graphs having
f
faces”. Then
S
is a statement about positive integers
f
, and we shall use the principle of mathematical induction to prove that
S
is true for all positive integers. This of course will mean that the theorem is true.

To begin, then. By the principle of mathematical induction we have to demonstrate two things, the first of which is that

That is, we have to show that
v
+
f
−
e
= 2 holds for all polygonal graphs having 1 face. But this is easy. A little thought will reveal that
N
₁
is the only polygonal graph having just one face (see
Exercise 1
), and for
N
₁
v
+
f
−
e
= 1 + 1 − 0 = 2 as required.

The second and final thing we have to demonstrate is that

Translated, we have to show that if
v
+
f
−
e
= 2 holds for all polygonal graphs having
k
faces, then
v
+
f
−
e
= 2 holds for all polygonal graphs having
k
+ 1 faces. Any “if...then...” statement is proved by accepting the first part and deducing the second part. This is no exception, so we will take as given the statement “
v
+
f
—
e
= 2 holds for all polygonal graphs having
k
faces.”

Now let
G
be an arbitrary polygonal
graph having
k
+ 1 faces. Remove some of the edges and vertices bordering the infinite face of
G
to produce a new polygonal graph
H
having one less face than
G
, so
H
has
k
faces. For example if
G
happened to look like
Figure 99a
,
H
might look like
Figure 99b
.

Figure 99

H
is a polygonal graph with
k
faces and we are given that
v
+
f
−
e
= 2 holds for all such graphs, so
v
_H
+
f
_H
−
e
_H
= 2, where the subscripts help us keep track of the graph whose vertices, faces, and edges we are counting. Our goal is to show that
v
_G
+
f
_G
−
e
_G
= 2, so let us try to relate
v
_G
,
f
_G
, and
e
_G
to the corresponding numbers for
H
.

G
has one more face than
H
because that's where
H
came from in the first place; thus
f
_G
and
f
_H
have the simple relationship
f
_G
=
f
_H
+ 1.
G
has more edges than
H
, but we don't know how many more. There's a long-standing tradition in mathematics wherein an unknown quantity is represented by “x”, so we'll go along with it and let × =
e
_G
−
e
_H
. Then
e
_G
and
e
_H
have the relationship
e
_G
=
e
_H
+ x.

Now think. Whenever edges and vertices are removed from a polygonal graph in order to produce another polygonal graph having one less face, the number of vertices removed is one less than the number of edges removed. For example in
Figure 99
, four edges and three vertices were removed. Do examples with pencil and paper until you're convinced. Thus
v
_G
−
v
_H
= × − 1, that is,
v
_G
=
v
_H
+ × − 1.

Having these relationships we can evaluate
v
_G
+
f
_G
−
e
_G
by substitution. The following string of equalities shows that when this is done the result is 2.

This completes the proof of statement (2). By the
principle of mathematical induction statement
S
is true for every positive integer, and therefore we have the theorem.

Theorem 9.
If
G
is planar and connected, but not polygonal
,
then v
+
f
−
e
= 2.

Proof
. Since
G
is not polygonal it has edges that border on only one face. Let the number of such edges be
n
. Add one vertex and two edges at each such location, producing anew graph
H
that is polygonal. For example if
G
were the graph of
Figure 100a
then
H
would look like
Figure 100b
.