You are here

A First Course in Graph Theory

Gary Chartrand and Ping Zhang
Dover Publications
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
John T. Saccoman
, on

Gary Chartrand continues to be prolific, even in retirement. This book is a revision of Introduction to Graph Theory, published in 2005. The book is a fine introduction to the field and is rich with real world applications of this interdisciplinary subject.

At the end of most chapters, there are “excursions” on such topics as graphs and matrices, graphs as groups (with the needed introduction to the algebraic terminology) and Instant Insanity. Three appendices provide some background in discrete mathematics, such as set theory, equivalence relations and proof techniques.

What sets the book apart are two of the excursions in particular, that offer the reader a historical perspective:

  • At the end of a chapter on transversability, Chartrand and Zhang write about the early books on graph theory, which gives the reader a perspective on this subject. In fact, they quote Oystein Ore, “The theory of graphs is one of the few fields of mathematics with a definite birth date,” referring to Leonhard Euler’s solution of the Koingsberg Bridge problem.
  • At the end of the chapter on Ramsey numbers and Turan’s Theorem, they include an excursion on Erdős numbers, the mathematicians’ take on the Kevin Bacon game. Included is an explanation of Erdős–Bacon numbers: a physicist with a Bacon number of 2 and an Erdős number of 3 has an Erdős-Bacon number of 2 + 3 = 5. All these serve as a friendly introduction to acquaintance graphs.

The book is appropriate for beginning undergraduates who desire to learn some graph theory. There are a good number of exercises with some solutions, and more than 100 references. This makes the text ideal for self-study as well. Having used prior editions to interest students in the subject, I look forward to recommending this update.

John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ.

1. Introduction
2. Degrees
3. Isomorphic Group
4. Trees
5. Connectivity
6. Traversability
7. Digraphs
8. Matchings and Factorization
9. Planarity
10. Coloring Graphs
11. Ramsy Numbers
12. Distance
13. Domination
Appendix 1
Appendix 2
Appendix 3
Solutions and Hints for Odd-Numbered Exercises
Index of Names
Index of Mathematical Terms
List of Symbols