Combinatorics and Graph Theory packs an immense amount in, offering largely self-contained introductions to both graph theory and combinatorics along with a shorter look at infinite combinatorics. This introduces the reader to two of the more intuitive and immediate areas of mathematics and gives them a highlights tour of the more esoteric realm of transfinite numbers and set theory. It tries to give a feel for the breadth of these topics, while highlighting key concepts and theorems.

There is little in the way of assumed knowledge, with both the combinatorics and graph theory developed from foundations, but the material gets progressively more difficult. Much of the graph theory would be within reach of an engaged secondary school student, though it does assume familiarity with mathematical notation. The combinatorics assumes comfort with matrices and infinite series, and for one section with group theory (an introduction there will work best as a refresher). And the extension to the infinite delves into set theory and mathematical logic, touching (without proofs) on striking results such as the construction of a finite combinatorial statement that can only be proven with assumptions about large (k-subtle) infinite cardinals.

The material in the first two parts provides a solid introduction to the basics and a glimpse of further topics. The graph theory covers planarity (Kuratowski's Theorem), colourings (chromatic polynomials), matchings, and Ramsey theory. The combinatorics centres generating functions, with introductions to Stirling numbers, Bell numbers, and so forth used to develop that, but also includes introductions to Polya theory, stable "marriage" problems, and combinatorial geometry. The third part stays connected to this, beginning with some simple results about infinite pigeonholes and trees and graphs, and an example of their use to prove finite results, before rapidly surveying axiomatic set theory, incompleteness, the hierarchy of cardinals, and infinite marriage problems.

The presentation is rigorous, with proofs included for almost everything until near the end, including a few longer multi-page proofs: Tutte's Theorem, Brook's Theorem, and so forth. And there is some discussion of open problems. The exercises are well motivated and range from the simple to the moderately challenging.

August 2021

External links:

- buy from Bookshop.org
- buy from Amazon.com or Amazon.co.uk
- share this review on Facebook or Twitter

Related reviews:

- books about mathematics
- books published by Springer