You are here

Combinatorics and Graph Theory

John M. Harris, Jeffry L. Hirst, and Michael J. Mossinghoff
Publication Date: 
Number of Pages: 
Undergraduate Texts in Mathematics
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Ioana Mihaila
, on

Combinatorics and Graph Theory is perhaps my favorite of all books I reviewed for MAA Reviews. I was thus naturally curious to see how the second edition looked like and if, as the authors put it, it was a “successful sequel” or not.

The new edition maintains the same three chapter structure: 1. Graph Theory, 2. Combinatorics, and 3. Infinite Combinatorics and Graphs. What is new is that each chapter has received several additions. Distance in graphs and trails, circuits etc. have been added to the Graph Theory part. The Combinatorics chapter has new sections on multinomial coefficients, the pigeonhole principle, as well as additions to the sections on Pólya’s theory and stable marriages. Finally, the Infinite Combinatorics and Graphs has a new comprehensive section on infinite marriage problems as well as a section on k–critical linear orderings. These additions come at a cost of about 130 new pages. For the amount of material contained, this is not a concern: at a total of 350 pages this is still the most comprehensive short combinatorics book I know.

When checking the new sections, I was happy to see that they were just as well written as the original, starting with basic definitions and statements and moving smoothly towards interesting problems. At the same time, the authors did a great job of integrating the new sections in the book while maintaining the flow of the text. Without a first edition in hand, the reader would not be able to point out the new material. When necessary, sections from the first edition have been rewritten. Even the cute mottos preceding each section have been occasionally changed for a better match. While this may appear mathematically irrelevant, it is proof of the care with which this book was revised.

Besides incorporating new sections, there are a few other notable changes. The Reference section at the end of each chapter has been expanded and organized by sections. Exercises have been added to a number of sections, for example the number of problems assigned to the principle of inclusion and exclusion has doubled. Both changes add value to the book.

In conclusion, the second edition of Combinatorics and Graph Theory has succeeded in adding relevant material and improving the overall organization of the book, while maintaining the flow of exposition, a great presentation style.

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

Preface to the Second Edition

Preface to the First Edition

1 Graph Theory
1.1 Introductory Concepts
1.2 Distance in Graphs
1.3 Trees
1.4 Trails, Circuits, Paths, and Cycles
1.5 Planarity
1.6 Colorings
1.7 Matchings
1.8 Ramsey Theory
1.9 References

2 Combinatorics
2.1 Some Essential Problems
2.2 Binomial Coefficients
2.3 Multinomial Coefficients
2.4 The Pigeonhole Principle
2.5 The Principle of Inclusion and Exclusion
2.6 Generating Functions
2.7 Pólya's Theory of Counting
2.8 More Numbers
2.9 Stable Marriage
2.10 Combinatorial Geometry
2.11 References

3 Infinite Combinatorics and Graphs
3.1 Pigeons and Trees
3.2 Ramsey Revisited
3.3 ZFC
3.4 The Return of der König
3.5 Ordinals, Cardinals, and Many Pigeons
3.6 Incompleteness and Cardinals
3.7 Weakly Compact Cardinals
3.8 Infinite Marriage Problems
3.9 Finite Combinatorics with Infinite Consequences
3.10 k-critical Linear Orderings
3.11 Points of Departure
3.12 References