Richard J. Trudeau - 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'.5dc20

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

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 didnt, if you feel there must be something to mathematics if only you knew what it was, then theres a good chance youll 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 youve 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 experience with plane geometry. Again no specific knowledge is required, just a feeling for how the game is played.

.

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 theorys terminology is still in flux and I have modeled mine more or less after Hararys.

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 well talk about it. In well 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 dont 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 dont hear about the fascinating intellectual game that lies beneath it all.

Earlier I implied that Euclidean geometryhigh 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 didnt 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 thats 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 theorems 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 isnt all that easy to learn from.