To honor Walter Rudin's contributions to mathematics education, McGrawHill has created the Walter Rudin Student Series in Advanced Mathematics. Chartrand and Zhang's Introduction to Graph Theory is one of the first books in this series. Being part of this series (or, for that matter, any series invoking Rudin's name) sets up rather high expectations. To the authors' credit, this book meets these expectations.
The authors' goals are to introduce undergraduates to the discipline of graph theory, informing them of the subject — as well as the people who shaped it — and then showing some of its applications. The text is very well written, accessible to undergraduate, and perhaps even some high school, students (provided they can keep track of the many terms that are used). The authors make good use of pictures and diagrams. They also adopt what is increasingly becoming a common practice: labeling proof techniques. Thus after the term Proof we see something like [direct proof] or [proof by contradiction] or [proof by minimum counterexample].
The lives of some of the people who have played major roles in the development of graph theory are discussed throughout the text. These are often done within a section. Personally, I prefer these diversions to either be boxed off to the side or in their own section. Placing them within a section makes it feel like a distraction. (The diversions are interesting, to be sure — just distracting.)
The topics covered in the book are isomorphic graphs, trees, connectivity and Menger's Theorem, Eulerian and Hamiltonian graphs, digraphs, graph factorization, planarity, graph coloring, Ramsey numbers, the notion of distance in a graph, and domination numbers. Each section contains several exercises, many along the lines of "construct a graph with the following properties…" And each chapter ends with a section or two of excursions and/or explorations, in which the students get to see some of the applications of the theory from the chapter. In addition to all of this, there are three appendices which review the notion of logic and proofs, a section with solutions and hints for oddnumbered problems, twelve pages of references, an index of names, an index of mathematical terms, and a list of symbols. This is probably just about as ideal a text as one could have in an introductory course on graph theory. And, as a whole, this book makes for a fine entry in the Walter Rudin Student Series in Advanced Mathematics.
Donald L. Vestal is Associate Professor of Mathematics at Missouri Western State University. His interests include number theory, combinatorics, and a deep admiration for the crimefighting efforts of the Aqua Teen Hunger Force. He can be reached at vestal@missoriwestern.edu
