Introduction to Graph Theory

INTRODUCTION TO GRAPH THEORY

INTRODUCTION TO GRAPH THEORY

Richard J. Trudeau

DOVER PUBLICATIONS, INC.

New York

Copyright

Copyright © 1993 by Richard J. Trudeau.

Copyright © 1976 by the Kent State University Press.
All rights reserved.

Bibliographical Note

This Dover edition, first published in 1993, is a slightly corrected, enlarged republication of the work first published by The Kent State University Press, Kent, Ohio, 1976. For this edition the author has added a new section, “Solutions to Selected Exercises,” and corrected a few typographical and graphical errors.

Library of Congress
Cataloging-in-Publication
Data

Trudeau, Richard J.

Introduction to graph theory / Richard J. Trudeau.

p. cm.

Rev. ed. of: Dots and lines, 1976.

Includes bibliographical references and index.

ISBN-13: 978-0-486-67870-2

ISBN-10: 0-486-67870-9

1. Graph theory. I. Trudeau, Richard J. Dots and lines. II. Title.

QA166.T74 1993

511
'
.5—dc20

93-32996

CIP

Manufactured in the United States by Courier Corporation
67870908
www.doverpublications.com

To Dick Barbieri and Chet Raymo

TABLE OF CONTENTS

Preface

1.
     
PURE MATHEMATICS

Introduction
. . .
Euclidean Geometry as Pure Mathematics
. . .
Games
. . .
Why Study Pure Mathematics?
. . .
What's Coming
. . .
Suggested Reading

2.
     
GRAPHS

Introduction
. . .
Sets
. . .
Paradox
. . .
Graphs
. . .
Graph Diagrams
. . .
Cautions
. . .
Common Graphs
. . .
Discovery
. . .
Complements and Subgraphs
. . .
Isomorphism
. . .
Recognizing Isomorphic Graphs
. . .
Semantics
. . .
The Number of Graphs Having a Given
v
. . .
Exercises
. . .
Suggested Reading

3.
     
PLANAR GRAPHS

Introduction
. . .
UG
,
K
₅
, and the Jordan Curve Theorem
. . .
Are There More Nonplanar Graphs?
. . .
Expansions
. . .
Kuratowski's Theorem
. . .
Determining Whether a Graph is Planar or Nonplanar
. . .
Exercises
. . .
Suggested Reading

4.
     
EULER'S FORMULA

Introduction
. . .
Mathematical Induction
. . .
Proof of Euler's Formula
. . .
Some Consequences of Euler's Formula
. . .
Algebraic Topology
. . .
Exercises
. . .
Suggested Reading

5.
     
PLATONIC GRAPHS

Introduction
. . .
Proof of the Theorem
. . .
History
. . .
Exercises
. . .
Suggested Reading

6.
     
COLORING

Chromatic Number
. . .
Coloring Planar Graphs
. . .
Proof of the Five Color Theorem
. . .
Coloring Maps
. . .
Exercises
. . .
Suggested Reading

7.
     
THE GENUS OF A GRAPH

Introduction
. . .
The Genus of a Graph
. . .
Euler's Second Formula
. . .
Some Consequences
. . .
Estimating the Genus of a Connected Graph
. . .
g
-Platonic Graphs
. . .
The Heawood Coloring Theorem
. . .
Exercises
. . .
Suggested Reading

8.
     
EULER WALKS AND HAMILTON WALKS

Introduction
. . .
Euler Walks
. . .
Hamilton Walks
. . .
Multigraphs
. . .
The Königsberg Bridge Problem
. . .
Exercises
. . .
Suggested Reading

Afterword

Solutions to Selected Exercises

Index

Special symbols

PREFACE

This book is about pure mathematics in general, and the theory of graphs in particular. (“Graphs” are networks of dots and lines;
*
they have nothing to do with “graphs of equations.”) I have interwoven the two topics, the idea being that the graph theory will illustrate what I have to say about the nature and spirit of pure mathematics, and at the same time the running commentary about pure mathematics will clarify what we do in graph theory.

I have three types of reader in mind.

First, and closest to my heart, the mathematically traumatized. If you are such a person, if you had or are having a rough time with mathematics in school, if you feel mathematically stupid but wish you didn't, if you feel there must be
something
to mathematics if only you knew what it was, then there's a good chance you'll find this book helpful. It presents mathematics under a different aspect. For one thing, it deals with
pure
mathematics, whereas school mathematics (geometry excepted) is mostly
applied
mathematics. For another, it is a more qualitative than quantitative study, so there are few calculations.

Second, the mathematical hobbyist. I think graph theory makes for marvelous recreational mathematics; it is intuitively accessible and rich in unsolved problems.

Third, the serious student of mathematics. Graph theory is the oldest and most geometric branch of topology, making it a natural supplement to either a geometry or topology course. And due to its wide applicability, it is currently quite fashionable.

The book uses some algebra. If you've had a year or so of high school algebra that should be enough. Remembering specifics is not so important as having a general familiarity with equations and inequalities. Also, the discussion in
Chapter 1
presupposes some
experience with plane geometry. Again no specific knowledge is required, just a feeling for how the game is played.

Chapter 7
is intended for the more mathematically sophisticated reader. It generalizes
Chapters 3–6
. It is more conceptually difficult and concisely written than the other chapters. It is not, however, a prerequisite for
Chapter 8
.

The exercises range from trivial to challenging. They are not arranged in order of difficulty, nor have I given any other clue to their difficulty, on the theory that it is worthwhile to examine them all.

The suggested readings are nontechnical. Those that have been starred are available in paperback.

There are a number of more advanced books on graph theory, but I especially recommend
Graph Theory
by Frank Harary (Addison-Wesley, 1969). It contains a wealth of material. Also, graph theory's terminology is still in flux and I have modeled mine more or less after Harary's.

Richard J. Trudeau

July 1975

*
This book was originally published under the title
Dots and Lines
.

1. PURE MATHEMATICS

Introduction

This book is an attempt to explain pure mathematics. In this chapter we'll talk about it. In
Chapters 2–8
we'll
do
it.

Most pre-college mathematics courses are oriented toward solving “practical” problems, problems like these:

A train leaves Philadelphia for New York at 3:00 PM and travels at 60 mph. Another train leaves New York for Philadelphia at 3:30 PM and travels at 75 mph. If the distance between the cities is 90 miles, when and at what point will the trains pass?

If a 12-foot ladder leaning against a house makes a 75° angle with the ground, how far is the foot of the ladder from the house and how far is the top of the ladder from the ground?

Mathematics that is developed with an eye to practical applications is called “applied mathematics”. With the possible exception of Euclidean geometry, pre-college mathematics is usually applied mathematics.

There is another kind of mathematics, called “pure mathematics”, which is a charming little pastime from which some people derive tremendous enjoyment. It is also the basis for applied mathematics, the “mathematics” part of applied mathematics. Pure mathematics is
real
mathematics.

To understand what mathematics is, you need to understand what pure mathematics is. Unfortunately, most people have either seen no pure mathematics at all, or so little that they have no real feeling for it. Consequently most people don't really understand mathematics; I think this is why so many people are afraid of mathematics and
quick to proclaim themselves mathematically stupid.

Of course, since pure mathematics is the foundation of applied mathematics, you can see the pure mathematics beneath the applications if you look hard enough. But what people see, and remember, is a matter of emphasis. People are told about bridges and missiles and computers. Usually they don't hear about the fascinating intellectual game that lies beneath it all.

Earlier I implied that Euclidean geometry—high school geometry— might be an example of pure mathematics. Whether it is or not again depends on emphasis.

Euclidean geometry as pure mathematics

What we call “Euclidean geometry” was developed in Greece between 600 and 300 B.C., and codified at the end of that period by Euclid in
The Elements. The Elements
is the archetype of pure mathematics, and a paradigm that mathematicians have emulated ever since its appearance. It begins abruptly with a list of definitions, followed by a list of basic assumptions or “axioms” (Euclid states ten axioms, but there are others he didn't write down). Thereafter the work consists of a single deductive chain of 465 theorems, including not only much of what was known at that time of geometry, but algebra and number theory as well. Though that's quite a lot for one book, people who read
The Elements
for the first time often get a feeling that things are missing: it has no preface or introduction, no statement of objectives, and it offers no motivation or commentary. Most strikingly, there is no mention of the scientific and technological uses to which many of the theorems can be put, nor any warning that large sections of the work have no practical use at all. Euclid was certainly aware of applications, but for him they were not an issue. To Euclid a theorem was significant, or not, in and of itself; it did not become more significant if applications were discovered, or less so if none were discovered. He saw applications as external factors having no bearing on a theorem's inherent quality. The theorems are included
for their own sake,
because they are interesting in themselves. This attitude of self-sufficiency is the hallmark of pure mathematics.

The Elements
is the most successful textbook ever written. It has gone through more than a thousand editions and is still used in some parts of the world, though in this country it was retired around the middle of the nineteenth century. It is amazing that it was used as
a school text at all, let alone for 2200 years, as it was written for adults and isn't all that easy to learn from.

Of the modern texts that have replaced
The Elements
, many are faithful to its spirit and present geometry as pure mathematics,
ars gratia artis.
There are others, however, that have sandwiched around Euclid's work long discussions of the “relevance” and “practicality” of geometry, complete with pictures of office buildings and space capsules and the suggestion that geometry is primarily a branch of engineering. Of course, applied geometry is a perfectly valid science, but I can't help objecting to such books on the ground that they rob school children of their only encounter with pure mathematics.

Despite this problem, in the next section I shall use Euclidean geometry as an example of pure mathematics, as it is the branch of pure mathematics with which you are most likely to be familiar.

Games

Basically pure mathematics is a box of games. At last count it contained more than eighty of them. One of them is called “Euclidean geometry”. In this section I will compare Euclidean geometry to chess, but you won't have to be a chessplayer to follow the discussion.

Games have four components: objects to play with, an opening arrangement, rules, and a goal. In chess the objects are a chessboard and chessmen. The opening arrangement is the arrangement of the pieces on the board at the start of the game. The rules of chess tell how the pieces move; that is, they specify how new arrangements can be created from the opening arrangement. The goal is called “checkmate” and can be described as an arrangement having certain desirable properties, a “nice” arrangement.