Introduction to Graph Theory (3 page)

Pure mathematics is a pleasant way to pass the time until the end. And to me that makes it very serious, very important indeed.

What's coming

Talking about pure mathematics isn't enough. To really understand what it is, you have to do it. That's why this book has seven more chapters.

In the pages ahead we shall develop the rudiments of one rather modest game from the pure mathematics game-box. It has the unfortunate name “graph theory”. The name is unfortunate because it is misleading. The objects with which the game is played are called “graphs”, which is also the name given to the pictures of equations drawn in high school algebra courses. “Graph” in our sense of the word is not a picture of an equation, but rather a network of dots and lines. “Network theory” would be a better name for our game. Nevertheless the official name of the game is “graph theory”, and mathematicians just have to remember that the “graph” of “graph theory” is not an algebraic graph. You'll appreciate the difference after reading
Chapter 2
.

Pure mathematics is a
big
game-box. I selected graph theory because it has several features that seemed desirable for this kind of book:

Graph theory is new; the bulk of it has been developed since 1890.

Graphs are simple, intuitively accessible things. In a book of this size we can develop enough graph theory to prove several spectacular theorems, and to half-prove several others.

Graph theory's frontier is easily reached, and you will find yourself, probably for the first time, thinking about famous unsolved problems.

If, like so many people, you dislike mathematics, it may be that you merely dislike applied mathematics, in which case you'll enjoy working your way through the chapters ahead. But mathematics books don't read like novels, so take your time.

If, on the other hand, you like mathematics, it may be that you like only applied mathematics, in which case you won't enjoy this book at all. Though graph theory has many applications (to electrical circuitry, chemistry, industrial management, linear programming, game theory, transportation networks, statistical mechanics, social psychology, and more) we're going to ignore them. After all, the book is supposed to be an antidote for an overdose of applied mathematics.

By this book I hope to influence your present attitude toward mathematics. Many people have a distorted notion of the nature and spirit of mathematics. Whether after reading the book you like or dislike mathematics is beside the point. My goal is rather that you form your attitude toward the subject in response to a clear image of it, not a phantasm.

Suggested reading

*A Mathematician's Apology
by G. H. Hardy (Cambridge University Press, 1967). A once-great has-been's defense of his life's work. I highly recommend it.

*Part II of
Fantasia Mathematica,
edited by Clifton Fadiman (Simon & Schuster, 1958). Part II is a collection of science-fiction stories with mathematical premises.

*
Mathematics in Western Culture
by Morris Kline (Oxford University Press, 1964). Kline argues that mathematics has been a major cultural force in the West, influencing not only science and philosophy, but religion, politics, painting, music, and literature as well.

*
The Nature and Growth of Modern Mathematics
(2 vols.) by Edna E. Kramer (Fawcett, 1970).

*
Philosophy of Mathematics
by Stephen F. Barker (Prentice-Hall, 1964).

*
Laws of Form
by G. Spencer Brown (Bantam, 1973). Heavy going; brilliant.

2. GRAPHS

Introduction

The things in
Figure 1
are called “graphs”, and are typical of what we will be playing with. Despite the name, they are unrelated to the pictures of equations drawn in high school algebra courses. To quickly convince you of this, I mention that we will consider graphs a), b), and c) to be identical (the word we will use is “isomorphic”), though if drawn in cartesian coordinates they would depict three different equations. In order to define “graph” more precisely, we must first discuss “sets”.

Sets

Definition 1
. A
set
is a collection of distinct objects, none of which is the set itself.

If you've encountered sets before you may find the last part of the definition a bit puzzling. We'll return to it in the next section, but for now suffice it to say that we intend to exclude collections like
A
= {1, 2, 3,
A
}.

The words “collection” and “object” are left undefined. Strictly speaking, therefore, we don't know what we're talking about. That's the way it is with pure mathematics. But there is implied an interpretation of “set” as being a bunch of things, an aggregate of entities, etc., and if your intuition feels more comfortable with something to hold onto (mine does), feel free to think of a set as being just what it sounds like. But be careful, for the words “collection” and “object” are used in a slightly unconventional fashion. We are allowing “collections” of infinitely many things, or just one thing, or even
no things. And an “object” need not be something we can smell or trip over; to a mathematician an “object” is anything conceivable, including numbers, unicorns, and Peter Pan. The only things left out are the inconceivable, for instance a figure which simultaneously has all the geometric properties of both a triangle and a circle. Everything else is acceptable.

Figure 1

A set is usually denoted by listing the names of the objects, separated by commas, within a pair of braces. So

{12, q, $, Empire State Building, 9, King Arthur}

is a set. Notice that the objects, which are called the elements of the set, need not have anything in common; mathematical sets are not like sets of luggage. Usually we give sets names to avoid a lot of writing when we subsequently refer to them. Thus one might say, “Let A = {12, q, $, Empire State Building, 9, King Arthur}.” This is the beginning of mathematical notation, something which, like any other shorthand, can be more confusing than helpful if not learned gradually as it comes along. Definitions are just another version of the same thing. I recommend that you memorize (yes!) the meanings of all new terms and symbols when they first appear.

Definition 2
. A set containing no elements is called a
null set
or an
empty set
.

An empty set plays the same role in set theory that 0 plays in arithmetic, but you must be careful not to confuse the two. An empty set is a set; 0 is a number. They are of completely different species. Think of it this way: 0 is a number that tells you how many objects there are in an empty set.

Definition 3
.
A
set
A
is said to be a subset of a set
B
, denoted “
A
⊂
B
”, if every element of
A
is also an element of
B
.

Example
. If
A
= {1, 2, 3} and
B
= {&, 3, +, 1, 2}, then
A
⊂
B
,
A
⊂
A
, and
B
⊂
B
. Notice that every set is a subset of itself.

Convention
. We agree to consider an empty set to be a subset of every set.

This “convention” can in fact be proved, but only by a logical contortion that seems inappropriate at the present. Thus it is a “convention” instead of a “theorem”.

Example
. If
J
is an empty set and
A
and
B
are the sets of the previous example, then
J
⊂
A
,
J
⊂
B
, and
J
⊂
J
.

Definition 4
.
A
set
A
is said to be equal to a set
B
, denoted “
A
=
B
”, if
A
⊂
B
and
B
⊂
A
.

Thus
A
=
B
if
A
and
B
consist of exactly the same objects. It follows that the order in which the elements of a set appear is irrelevant. For example, {1, 2, 3} = {2, 1, 3} since {1, 2, 3} ⊂ {2, 1, 3} and {2, 1, 3} ⊂ {1, 2, 3}.

Theorem 1
. There is only one empty set.

Proof. Let
J
and
K
be empty sets. Then by the Convention,
J
⊂
K
and
K
⊂
J
, so
J
=
K
by
Definition 4
. Thus all empty sets are equal; that is, there is really only one empty set.

Notation
. The empty set (we had to say “an empty set” before, but now we can say “the empty set”) shall be denoted by “
ø
” or “{ }”.

Use either notation at your whim, but be careful not to combine them. “{
ø
}” would be interpreted by a mathematician as signifying a set containing one element, that element being the symbol
ø
.

In view of the word “distinct” in
Definition 1
, collections like {1, 3, 3, &, 407}, in which an object is listed more than once, are not sets. The definition was designed to exclude this sort of thing because
“{1, 3, 3, &, 407}” is a redundancy. We are being told twice that the collection contains the number 3.

All the set theory we'll need to talk about graphs has now been developed. But before going on I want to take time out and explain why in pure mathematics we are so excruciatingly careful about definitions and proofs (something you may have already noticed). In the process I'll explain the reason for that last clause in
Definition 1
. You may find parts of the next section a little involved, but I think my point is important and I encourage you to persist.

Paradox

The story begins in the sixth century B.C. with the Pythagoreans, a community of men and women founded by Pythagoras at Crotona in southern Italy. The Pythagoreans shared quasi-religious rituals, dietary laws, and devotion to mathematics as the key to understanding nature. It is they who first discovered that intuition and logic can disagree.

The Pythagorean Paradox
.
It happened like this. Let
AB
and
CD
be two finite straight lines. We will say that a finite straight line
XY
is a “common measure” of
AB
and
CD
if there are whole numbers
m
and
n
so that
XY
laid down
m
times is the same length as
AB
, and
XY
laid down
n
times is the same length as
CD
. For example, if
AB
were a yard long and
CD
10 inches, a line segment
XY
of inches would be a common measure with
m
= 18 and
n
= 5; for laying down
XY
eighteen times would produce a length of 36 inches, the same as
AB
, and laying down
XY
five times would produce a length of 10 inches, the same as
CD
.
XY
= 1/4 inch would be another common measure, this time with
m
= 144 and
n
= 40. It was intuitively evident to the Pythagoreans, and as I write it is intuitively evident to me, that a common measure can be found for any pair of finite straight lines—though of course it may be necessary to take
XY
quite small in order to measure both
AB
and
CD
exactly. Since
AB
/
CD
=
m
(
XY
)/
n
(
XY
) =
m
/
n
, a “rational” number (that is, a quotient of whole numbers), what my intuition predicts is that the quotient of two lengths is always a rational number.

Now take a square with side equal to 1 and draw a diagonal. By the Pythagorean Theorem the length of the diagonal is √2 and so the quotient of the length of the diagonal and the length of one of the sides is also √2. If the Pythagoreans' intuition and mine are correct
in asserting that the quotient of two lengths is always a rational number, √2 must be a rational number. But one of the later Pythagoreans (probably Hippasus of the fifth century B.C.) discovered, by an argument not based primarily on intuition, that √2 cannot be a rational number.