Gary Chartrand - A First Course in Graph Theory

Copyright

Copyright 2012 by Gary Chartrand and Ping Zhang
All rights reserved.

Bibliographical Note

This Dover edition, first published in 2012, is a revised and corrected republication of Introduction to Graph Theory , originally published in 2005 by McGraw-Hill Higher Education, Boston.

Library of Congress Cataloging-in-Publication Data

Chartrand, Gary.

A first course in graph theory / Gary Chartrand and Ping Zhang.

p. cm.

Previous edition published as: Introduction to graph theory. Boston : McGraw-Hill Higher Education, c2005

Includes bibliographical references and index.

ISBN-13: 978-0-486-48368-9

ISBN-10: 0-486-48368-1

1. Graph theory. I. Zhang, Ping, 1957 II. Chartrand, Gary. Introduction to graph theory. III. Title.

QA166.C455 2012
511.5dc23

2011038125

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

Dedicated to the memory of the many mathematicians whose contributions, linked in a variety of ways, have led to the development of graph theory.

From Knigsberg to Knigs book ,
So runs the graphic tale .
And still it grows more colorful

Blanche Descartes (1969)

Perhaps its not so surprising that when we (the authors) were learning mathematics, we thought that we were being taught some well-known facts facts that had been around forever. It wasnt until later that we started to understand that these facts (the word theorem was beginning to become part of our vocabulary) had not been around forever and that people had actually discovered these facts. Indeed, names of people were becoming part of the discussion.

Mathematics has existed for many centuries. In the ancient past, certain cultures developed their own mathematics. This was certainly the case with Egypt, Babylonia, Greece, China, India and Japan. In recent centuries, there has become only one international mathematics. It has become more organized and has been divided into more clearly defined areas (even though there is significant overlap). While this was occurring, explanations (proofs) as to why mathematical statements are true were becoming more structured and clearly written.

The goal of this book is to introduce undergraduates to the mathematical area called graph theory , which only came into existence during the first half of the 18th century. This area didnt start to develop into an organized branch of mathematics until the second half of the 19th century and there wasnt even a book on the subject until the first half of the 20th century. Since the second half of the 20th century, however, the subject has exploded.

It is our intent to describe some of the major topics of this subject to you and to inform you of some of the people who helped develop and shape this area. In the beginning, most of these people were just like you students who enjoyed mathematics but with a great sense of curiosity. As with everything else (though not as often talked about), mathematics has its non-serious side and weve described some of this as well. Even the most brilliant mathematicians dont know everything and weve presented some topics that have not been well-studied and in which the answers (and even the questions) are not known. This will give you the chance to do some creative thinking of your own. In fact, maybe the next person who will have an influence on this subject is you.

Part of what makes graph theory interesting is that graphs can be used to model situations that occur within certain kinds of problems. These problems can then be studied (and possibly solved) with the aid of graphs. Because of this, graph models occur frequently throughout this textbook. However, graph theory is an area of mathematics and consequently concerns the study of mathematical ideas of concepts and their connections with each other. The topics and results we have included were chosen because we feel they are interesting, important and/or are representative of the subject.

As we said, this text has been written for undergraduates. Keeping this in mind, we have included a proof of a theorem if we believe it is appropriate, the proof technique is informative and if the proof is not excessively long. We would like to think that the material in this text will be useful and interesting for mathematics students as well as for other students whose areas of interest include graphs. This text is also appropriate for self-study.

We have included three appendixes. In describes methods of proof. We understand how frustrating it is for students (or anyone!) who try to read a proof that is not reader-friendly and which leaves too many details for the reader to supply. Consequently, we have endeavored to give clear, well-written proofs.

Although this can very well be said about any area of mathematics or indeed about any scholarly activity, we feel that appreciation of graph theory is enhanced by being familiar with many of the people, past and present, who were or are responsible for its development. Consequently, we have included several remarks that we find interesting about some of the people of graph theory. Since we believe that these people are part of the story that is graph theory, we have discussed them within the text and not simply as footnotes. We often fail to recognize that mathematics is a living subject. Graph theory was created by people and is a subject that is still evolving.

There are several sections that have been designated as Excursion. These can be omitted with no negative effect if this text is being used for a course. In some cases, an Excursion is an area of graph theory we find interesting but which the instructor may choose not to discuss due to lack of time or because its not one of his or her favorites. In other cases, an Excursion brings up a sidelight of graph theory that perhaps has little, if any, mathematical content but which we simply believe is interesting.

There are also sections that we have designated as Exploration. These sections contain topics with which students can experiment and use their imagination. These give students opportunities to practice asking questions. In any case, we believe that this might be fun for some students.

As far as using this text for a course, we consider the first three chapters as introductory. Much of this could be covered quite quickly. Students could read these chapters on their own. It isnt necessary to cover connectivity and Mengers Theorem if the instructor chooses not to do so. can be covered according to the instructors interest.

Solutions or hints for the odd-numbered exercises in the regular sections of the text, references, an index of mathematical terms, an index of people and a list of symbols are provided at the end of the text.

It was because of discussions we had with Robert Ross that we decided to write An Introduction to Graph Theory. We thank him for this and for his encouragement. We especially thank John Grafton, Senior Reprint Editor at Dover Publications, whose encouragement led us to revise the book, with its new title A First Course in Graph Theory. We are most grateful to the reviewers of the original edition who gave us many valuable suggestions: Jay Bagga, Ball State University; Richard Borie, University of Alabama; Anthony Evans, Wright State University; Mark Ginn, Appalachian State University; Mark Goldberg, Rensselaer Polytechnic Institute; Arthur Hobbs, Texas A&M University; Garth Isaak, Lehigh University; Daphne Liu, California State University, Los Angeles; Alan Mills, Tennessee Technological University; Dan Pritikin, Miami University; John Reay, Western Washington University; Yue Zhao, University of Central Florida.