Search MAA Reviews:
A First Course in Graph Theory
Gary Chartrand and Ping Zhang
Publisher: Dover Publications (2012)
Details: 450 pages, Paperback
Topics: Graph Theory
MAA Review[Reviewed by John T. Saccoman, on 12/17/2012]
Gary Chartrand continues to be prolific, even in retirement. This book is a revision of his classic Dover text Introductory Graph Theory. 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.