Introduction to Graph Theory (21 page)

Figure 92

Figure 93

Suggested reading

On Mathematical Jargon

*“New Names for Old” by Edward Kasner and James R. Newman, reprinted in volume 3 of
The World of Mathematics
edited by James R. Newman (Simon and Schuster, 1956).

On Impossibility

*The Borders of Mathematics
by Willy Ley (Pyramid Publications, 1967).

4. EULER'S FORMULA

Introduction

Leonhard Euler (pronounced “oiler”, 1707–1783) is judged
by all to have been the most productive, and by many to have been the best, mathematician of modern times. He was Swiss, but spent much of his life in Russia because he had a big family and Catherine the Great offered him a lot of money. His paper “The Seven Bridges of Königsberg” (1736), which we will discuss in
Chapter 8
, is the earliest known work on the theory of graphs.

The theorem now known as Euler's Formula was proved by Euler in 1752. It is one of the classic theorems of elementary mathematics and plays a central role in the next three chapters of this book. To state it we need some preliminary definitions.

Definition 21
. A
walk
in a graph is a sequence
A
₁
A
₂
A
₃
...
A
_n
of not necessarily distinct vertices in which
A
₁
is joined by an edge to
A
₂
,
A
₂
is joined by an edge to
A
₃
, ..., and
A
_{n
− 1}
is joined by an edge to
A
_n
. The walk
A
₁
A
₂
A
₃
...
A
_n
is said to join
A
₁
and
A
_n
.

Examples
. 1) Let
G
be the graph of
Figure 94a
. Then
DCAB
,
ACDCACD
,
ABABAB
,
ACA
, and
BACDCBCD
are all walks in
G
.
ACDAB
is not a walk because the third vertex in the sequence is not adjacent to the fourth.

2) Any sequence of distinct vertices in
K
_v
is a walk.

3) A null graph
N
_v
has no walks.

Definition 22
. A graph is said to be
connected
if every pair of vertices is joined by a walk. Otherwise a graph is said to be
disconnected.

Examples.
1) The graphs of
Figure 94a
and
94b
are connected.

2) The graphs of
Figure 95a
and
95b
are disconnected, for in each case it is possible to find a pair of vertices not joined by any walk.

Figure 94

Figure 95

3) Every cyclic graph is connected, as is every complete graph.

4) Except for
N
₁
, all null graphs are disconnected.

You may be puzzled at my statement that
N
₁
(also known as
K
₁
) is connected, as the definition refers to
pairs
of vertices. The reason is that the system
of logic used in the mainstream of mathematics contains the Law of Excluded Middle, whereby every properly formed statement is either true or false and there is no third possibility. In everyday life this is not always the case; for example I don't think that the statement “George Washington stopped beating his wife in March 1790” fits very well into either category. But in mathematics there are only the two categories, so being “true” is the same as being “not false”. It follows that
N
₁
is connected, and we might argue as follows.

In order for
N
₁
to be disconnected it would, by
Definition 22
, have to contain two vertices which are not joined by any walk. But
N
₁
doesn't even contain two vertices, let alone two not joined by a walk. So the statement “
N
₁
is connected” is not false and must therefore be true.

Intuitively, connected graphs are in one piece and disconnected graphs aren't. The graph of
Figure 95a
looks at first as if it were in one piece, but it really isn't because it is isomorphic to a graph formed by placing two copies of
K
₃
next to one another.

Definition 23.
When a planar graph is actually drawn in a plane without edge-crossings, it cuts the plane into regions called
faces
of the graph. The letter “
f
” shall denote the number of faces of a planar graph.

Implicit in this definition are two assumptions. One is that a planar graph, when drawn in a plane without edge-crossings, does indeed cut the plane into well-defined regions (a generalization of the Jordan Curve Theorem). The other assumption is that the number of regions is independent of the particular drawing. Without the first assumption it would be impossible to speak of “faces” at all. And without the second it would be impossible to speak of “the” (unique) number of faces of a specific planar graph. Neither need be assumed, for they can be proved. We will not do so, but please note that without at least knowing that such proofs exist, the definition could not have been validly made.

Examples.
In each of the graphs in
Figure 96
the faces have been numbered. The first graph has
f
= 7 and the second
f
= 10. Note that the exterior region is counted as a face; it is sometimes called “the infinite face”.

Two words of caution. First, only planar graphs have faces; the
word “face” is meaningless if used in reference to graph a) in
Figure 97
, because graph a) is nonplanar. Second, though all planar graphs do have faces,
Definition 23
defines them only in connection with
crossing-free drawings
of the planar graphs;
K
₄
does not have five faces, though it might appear that way in
Figure 97b
, because
97b
is not crossing-free (actually
K
₄
has
f
= 4 as you can see from
Figure 97c
).

Figure 96

Figure 97

The next definition is more convenient than necessary. We will use it to break the proof of Euler's Formula into two pieces, thereby making the proof easier to follow.

Definition 24
. A graph is
polygonal
if it is planar, connected, and has the property that every edge borders on two different faces.

Clearly an edge can border on no more than two faces, so what we are excluding are planar connected graphs having one or more edges that border on only one face.

Examples.
1) The graph of
Figure 96a
is not polygonal because it has two edges that border only on face 1 and another edge that borders only on face 3.

2) Every edge of
Figure 96b
borders on two faces, but it is not polygonal because it is disconnected.

3) No nonplanar graph has faces, so no nonplanar graph is polygonal.

4) The graphs of
Figure 98
are polygonal. Graph b.) would have to be redrawn without edge-crossings in order for its polygonal nature to become apparent.

Figure 98

Early mathematicians were amazed to discover that for any
circle whatever, no matter how small or large, the circumference
C
divided by the diameter
d
always has the same value, 3.14159 .... Of course they couldn't measure the quotient very accurately, but they did know that it was somewhere between
and
. In modern terms their discovery was that for circles
C
/
d
is constant, and the constant is 3.14159 ....