Benjamin Arthur - The Fascinating World of Graph Theory

THE FASCINATING WORLD OF GRAPH THEORY

THE FASCINATING WORLD OF GRAPH THEORY

Arthur Benjamin

Gary Chartrand

Ping Zhang

PRINCETON UNIVERSITY PRESS

PRINCETON AND OXFORD

Copyright 2015 by Princeton University Press

Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press, 6 Oxford Street, Woodstock, Oxfordshire, OX20 1TW

Background image Veerachai Viteeman / Shutterstock

All Rights Reserved

Library of Congress Cataloging-in-Publication Data

Benjamin, Arthur, author.

The fascinating world of graph theory / Arthur Benjamin, Gary Chartrand, Ping Zhang.

pages cm

Includes bibliographical references and index.

ISBN 978-0-691-16381-9 (hardcover : alk. paper) 1. Graph theory.

I. Chartrand, Gary, author. II. Zhang, Ping, 1957-author. III. Title.

QA166.B385 2015

511.5dc23

2014010927

British Library Cataloging-in-Publication Data is available

This book has been composed in ITC New Baskerville
Printed on acid-free paper.

press.princeton.edu

Typeset by S R Nova Pvt Ltd, Bangalore, India

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

Contents

Preface

M athematics rarely has the reputation we feel it deserves. To many, mathematics is an area that is, sadly, too difficult and too boring. It requires too much effort to learn and to understand. Its not as much fun as other subjects. In recent years there have been numerous articles written about how many American high-school students have been out-performed in mathematics and science by students from other nations. There have also been reports of a marked decrease in the number of Americans in colleges earning graduate degrees in mathematics. For whatever reason, not nearly enough talented American students have become sufficiently excited about mathematics. For many students, this is a missed opportunity. For the United States, this is a missed opportunity. There are many areas within mathematics and we happen to think that they are all exciting. Behind the many interesting theorems in each of these areas is a history of how these came abouta story of how some dedicated mathematicians discovered something of interest and importance. These theorems were often not only attractive to those who discovered them but in many cases unexpected to others. In many instances, these theorems turned out to be extraordinarily usefulboth within and outside of mathematics. Our goal in this book is to introduce you to one of the many remarkable areas of mathematics. It is with pleasure that we invite you to enter

The Fascinating World of Graph Theory.

Like every other scholarly field, mathematics is composed of a number of areas, similar in many ways, yet each having their own distinct characteristics. The areas with which you are probably most familiar include algebra, geometry, trigonometry and calculus. Learning and understanding these subjects may very well have required some effort on your part but, hopefully, it has been interesting as well. In fact, learning any subject should be fun. But where did these and all other areas of mathematics come from? The answer to this question is that they came from peoplefrom their curiosity, their imagination, their cleverness. Although many of these people were mathematicians, some were not. Sometimes they were studentslike all of us are (or were).

It is our goal here to introduce you to a subject to which you may have had little or no exposure: the field of graph theory. While we wish to show you how interesting this area of mathematics is, we hope to convince you that mathematics itself is not only interesting but can in fact be exciting. So come with us as we take you along on what we believe will be a fascinating journey through the area of graph theory. Not only do we want to introduce you to many of the interesting topics in this area of mathematics, but it is our desire to give you an idea of how these topics may have been discovered and the kinds of problems they can be used to solve.

Among the many things we discuss here is how often a rather curious problem or question can lead not only to a mathematical solution but to an entire topic in mathematics. While it is not our intention to describe some deep or advanced mathematics here, we do want to give an idea of how we can convince ourselves that certain mathematical statements are true.

is present a theorem often called the First Theorem of Graph Theory, dealing with what happens when the degrees of all vertices of a graph are added.

closes with a rather mysterious problem in graph theory that no one has been able to solve.

discusses the most fundamental property that a graph can possess, dealing with the idea that within the graph, travel is possible between every two locations. This brings up questions of the distance between locations in a graph and those locations that are far from or close to a given location. The chapter concludes with the rather humorous concept of Erds numbers, based on mathematicians who have done research with mathematicians who have done research with who have done research with the celebrated twentieth-century mathematician Paul Erds.

concerns the simplest structure that a connected graph can possess, leading us to the class of graphs called treesbecause they often look like trees. These graphs have connections to chemistry and can assist us in solving problems where certain decisions must be made at each stage in solving the problem. This chapter ends by discussing a practical problem, one that involves the least expensive highway system that would allow us to travel between any two locations in the system.

Graph theory has a rather curious history. Most acknowledge that this area began in the eighteenth century when the brilliant mathematician Leonhard Euler was introduced to and solved a problem referred to as the Knigsberg Bridge Problem and then went on to describe a considerably more complex problem. This led to a class of graphs named for Euler, which we study in . This chapter concludes with another well-known problem, the Chinese Postman Problem, which deals with minimizing the length of a round-trip that a letter carrier might take.

discusses a class of graphs named for a famous physicist and mathematician of the nineteenth century: Sir William Rowan Hamilton. Although Hamilton had very little to do with graph theory, it was he who came up with the idea of icosian calculus, which led him to inventing a game that involved finding round-trips around a dodecahedron in which every vertex is encountered exactly once. Beginning midway through the twentieth century, an explosion of theoretical results involving this concept occurred. This chapter ends with a discussion of a problem of practical importance, that of finding a shortest or least costly round-trip that visits all locations of a certain type.

Problems that ask whether some collection of objects can be matched in some way to another collection of objects are plentifulsuch as matching , gave rise in the late nineteenth century to the first consideration of graph theory as a theoretical area of mathematics and no doubt led to the term graph being used for the structure we discuss in this book. From this topic in graph theory, we can see how different types of schedulings are possible.

concerns problems of whether a graph can be divided into certain other kinds of graphs, primarily cycles. Whether some specific complete graphs can be divided into triangles in some manner was the situation encountered when, in the mid-nineteenth century, the mathematician Thomas Kirkman stated and then solved a problem often referred to as Kirkmans Schoolgirl Problem. There is a relationship between graph decomposition problems and a problem dealing with whether the vertices of a graph can be labeled with certain integers in a manner that produces a desirable labeling of its edges. This chapter ends with a tantalizing puzzle called Instant Insanity and how graphs can be utilized to solve it.