Brett Levett
The layout of this book is tailored for the readership at which it is aimed - students studying at university. At the end of each section there are sets of problems, with selected solutions at the end of the book. The problems fully reflect the content of each section and offer an interesting way of learning the material, as well as a challenging one, with clearly labelled harder problems. The book is written at a level to challenge pure mathematicians but also to give the casual reader interesting pieces of information. Although it is a textbook it transcends the usual dry and unapproachable aspects usually associated with this kind of literature, mainly in its extensive, but appropriate, use of diagrams. For a subject which is wholly concerned with graphs, much of the literature concerning graph theory mysteriously lacks the aforementioned diagrams instead relying on algebra and uninspiring text descriptions. This 'learning by example' approach, although embraced by many academic disciplines, has often been frowned upon by the mathematical fraternity making books like this the exception, sadly, rather than the rule.
As a first text in the topic of graph theory this book provides ample examples of applications and famous problems. For example using the Chinese postman problem, and the seemingly ubiquitous travelling salesman problem to illustrate the topics of Eulerian trials and Hamiltonian cycles respectively. The author uses an apt and witty quote from such luminaries as Shakespeare, Lewis Carroll and Benjamin Disraeli at the beginning of each chapter as if to put the reader at ease, for example at the start of chapter one, he uses Blaise Pascal's quote
The last thing one discovers in writing a book is what to put first.The layout of the text is intuitive as well as sensible with definitions, corollaries and theorems all in grey boxes and numbered in a way so as to prevent the reader having to flick through pages to see what the text refers to. Proofs are also well labelled and often have accompanying diagrams making the often intractable mathematics at least partially understandable.
There are thirty-three sections divided sensibly into nine chapters which clearly set out their content at the beginning. Chapter 1 provides an introduction, explaining in plain English exactly what a graph is, as well as gently setting out material from later chapters without rigorous definitions. The foundations of the subject are laid down in chapter 2 including the concepts of isomorphism, connectedness and adjacency. These are demonstrated by using three puzzles including the four cubes problem, where four cubes with coloured sides (using four colours) are stacked in such a way so that all four colours appear on each side of the stack. Chapter 3 analyses the properties of graphs including connectivity and Eulerian trails with the latter being illustrated with the famous Königsberg bridges problem, which asks whether you can cross each of seven bridges over the Königsberg river exactly once and return to your starting point. This chapter also introduces the notion of Hamiltonian graphs and cycles upon which so much in graph theory is based. The fourth chapter is dedicated to the topic of trees including Cayley's theorem and counting trees. As an interest to computer scientists and artificial intelligence enthusiasts the chapter shows the mathematical theory behind search trees, giving appropriate definitions of depth first and breadth first search. These first four chapters provide a basic foundation course that can either be used as background for the later chapters or as a crash course for someone who needs to learn the basics of graph theory quickly.
In chapters 5 and 6 the book focuses on the specific topics of planarity and colouring. The sections under planarity include Euler's formula, graphs on other surfaces and dual graphs. Chapter 6 uses one of the most famous puzzles in mathematics as an example on the subject of colouring. The puzzle is the four-colour problem, where given any map, is there a way of colouring each bounded area with one of four colours so that it doesn't border any other area with the same colour. This is certainly one of the most interesting chapters but requires some mathematical knowledge, although if the previous chapters have been read and understood this may not be necessary. Chapters 7 and 8 deal with digraphs and their applications, as with the previous chapter prior mathematical knowledge would be beneficial especially probability theory. The very fashionable Markov chains are given the graph theory treatment to illustrate how a simple digraph works. There is a whole chapter dedicated to the applications of digraphs, these include Hall's marriage theorem and network flows, the latter having important implications in many areas including transportation and communication. The final chapter in the book is the most irrelevant and difficult to understand. it concentrates on matroids but unlike the rest of the book this chapter contains no applications or puzzles, instead relying on an unacceptable amount of theory. If the book was written in the order it is presented then it seems that the author probably rushed the last chapter.
This book has a lot to offer in terms of a first textbook for students learning the subject of graph theory but also as an introduction for anybody needing to learn any of the material quickly. It is a well organised book with a gentle learning curve and sensible questions set at the end of each section. In summary, this book is very well written and has enough diagrams to make the subject matter approachable and easy to follow. In a discipline where tomes of algebra are common, this book stands out as an intelligent way of teaching its subject and is certainly one of the best in its particular area.
