Read Introduction to Graph Theory Online

**Authors: **Richard J. Trudeau

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

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**

Introduction

. . .

Euclidean Geometry as Pure Mathematics

. . .

Games

. . .

Why Study Pure Mathematics?

. . .

What's Coming

. . .

Suggested Reading

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

Introduction

. . .*UG*,

. . .

Are There More Nonplanar Graphs?

. . .

Expansions

. . .

Kuratowski's Theorem

. . .

Determining Whether a Graph is Planar or Nonplanar

. . .

Exercises

. . .

Suggested Reading

Introduction

. . .

Mathematical Induction

. . .

Proof of Euler's Formula

. . .

Some Consequences of Euler's Formula

. . .

Algebraic Topology

. . .

Exercises

. . .

Suggested Reading

Introduction

. . .

Proof of the Theorem

. . .

History

. . .

Exercises

. . .

Suggested Reading

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

Solutions to Selected Exercises

**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

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

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.

Thornbrook Park by Sherri Browning

Strategy by Freedman, Lawrence

The Constantine Affliction by T. Aaron Payton

La caza del meteoro by Julio Verne

The Death Ship by B. TRAVEN

Fall and Rise by Stephen Dixon

The Spring Cleaning Murders by Dorothy Cannell

Moon Love by Joan Smith

Save Me (Taken Series Book 1) by Cannavina, Whitney