You are here

Combinatorics and Graph Theory

John M. Harris, Jeffry L. Hirst, and Michael J. Mossinghoff
Springer Verlag
Publication Date: 
Number of Pages: 
Undergraduate Texts in Mathematics
[Reviewed by
Ioana Mihaila
, on

My first impression of the Harris, Hirst and Mossinghoff book was: this is what a textbook should be! The book is comprehensive without being overwhelming, the proofs are elegant, clear and short, and the examples are well picked.

The book is aimed at the upper-division undergraduate students and beginning graduate students. There are minimal prerequisites for the material covered — mainly some familiarity with proof-techniques. The book does require a degree of mathematical maturity from the reader. Unlike in typical lower undergraduate texts, the definitions are usually followed but just one representative example. There are no frivolous drill exercises at the end of the sections — most exercises ask for proofs, and the few computational ones are meant to illustrate results. In comparison to standard books written for a similar audience (Alan Tucker's Applied Combinatorics, Fred Roberts' Applied Combinatorics, Kenneth Bogart's Introductory Combinatorics), this text is much shorter and more streamlined.

Combinatorics and Graph Theory is structured into three main chapters: Graph Theory, Combinatorics, and Infinite Combinatorics and Graphs.

The Graph Theory section covers basic concepts, trees, planarity, colorings, matching and Ramsey theory. All this material is covered in a mere 84 pages. This is accomplished through a careful choice of topics, followed by a careful choice of results presented in each topic. For example, when discussing planarity, the authors move quickly from the definition, to Euler's formula, to Kuratowski's Theorem. I was impressed by the authors' ability to move so smoothly within each topic from the basic concepts to meaningful and difficult results.

The Combinatorics section covers permutations, combinations, binomial coefficients, principle of inclusion-exclusion, generating functions, Pólya's Theory of counting, Stirling (and other kinds of) numbers, and stable marriages. While the basic counting techniques are covered briefly, generating functions are given great weight. In fact, most proofs and computations in this part of the book (including the ones from the recurrence relations section, and all the special numbers calculations) are done elegantly using generating functions — a trait of the book that I really enjoyed!

Finally, the chapter on Infinite Combinatorics and Graph Theory introduces the reader to the ZFC system, ordinals, cardinals and Gödel's incompleteness theorems. The authors include this unusual chapter in the book with at least two purposes: to show how different infinite combinatorics reasoning is from finite combinatorics, and to illustrate how infinite combinatorics can be used to prove difficult results from finite combinatorics (for example the existence of finite Ramsey numbers). It seems unlikely, however, that this chapter could be covered within a typical one semester undergraduate course, due to both time constraints and the difficulty of material.

My only wish about the book would be a companion problem book. Generally, I feel that no book has enough exercises. In the case of this text, the exercises are very well chosen to illustrate the sections, and probably adding too many to the current list would make the selection weaker. However, most students need more practice and variation, and a problem book (or perhaps web resources?) would do the job without interfering with the flow of the material.

Last, but not least, a few words about the exposition of the book. I have already mentioned that the book is beautifully written mathematically: it is clear, and streamlined. At the same time, the writing is pleasant and funny. Each chapter starts with a brief but concrete description of goals and applications (for example, the use of stable marriages algorithms in assigning medical students to hospitals for residences), which answer the perpetual question "what is this good for?" In addition, each section has a motto. I would be curious to know how the authors came up with the hilarious selection of quotes that they used. Let me give just a few examples:

At the beginning of the section on Colorings: "One fish, two fish, red fish, blue fish. — Dr. Seuss."

The Four Color Problem: "This doesn't sound too hard. — Star Wars."

Eulerian Numbers: "Look out football, here we come! Houston Oilers, number one! — The Houston Oilers' Fight Song."

Of course, some are more serious. The motto for the section on Three Basic Problems is "The mere formulation of a problem is far more essential than its solution... - Albert Einstein."

I would strongly recommend this book to anyone with an interest in combinatorics who has an appreciation for mathematical proofs, and the required patience to work through them. It is the ideal textbook for the motivated junior/senior audience, and otherwise a great reference book on the topic.

Ioana Mihaila ( is Assistant Professor of Mathematics at Cal Poly Pomona. Her research area is analysis, and she is interested in mathematics competitions.

Graph Theory: Introductory Concepts.- Trees.- Planarity.- Colorings.- Matchings.- Ramsey Theory.- References; Combinatorics: Three Basic Problems.- Binomial Coefficients.- The Principle of Inclusion and Exclusion.- Generating Functions.- Polya's Theory of Counting.- More Numbers.- Stable Marriage.- References; Infinite Combinatorics and Graph Theory: Pigeons and Trees.- Ramsey Revisited.- ZFC.- The Return of der Koenig.- Ordinals, Cardinals, and Many Pigeons.- Incompleteness and Coardinals.- Weakly Compact Cardinals.- Finite Combinatorics with Infinite Consequences.- Points of Departure.- References.