Introduction to Graph Theory 2nd Edition

Book 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

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, K5, 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

---

Download Ebook	Read Now	File Type	Upload Date
Download here Download Now here	Read Now	Epub	October 24, 2021

---

How to Read and Open File Type for PC ?