viii Preface
introductory text should be lean and concentrate on the essential, so as
to offer guidance to those new to the field. As a graduate text, moreover,
it should get to the heart of the matter quickly: after all, the idea is to
convey at least an impression of the depth and methods of the subject.
On the other hand, it has been my particular concern to write with
sufficient detail to make the text enjoyable and easy to read: guiding
questions and ideas will be discussed explicitly, and all proofs presented
will be rigorous and complete.
Atypical chapter, therefore, begins with a brief discussion of what
are the guiding questions in the area it covers, continues with a succinct
account of its classic results (often with simplified proofs), and then
presents one or two deeper theorems that bring out the full flavour of
that area. The proofs of these latter results are typically preceded by (or
interspersed with) an informal account of their main ideas, but are then
presented formally at the same level of detail as their simpler counter-
parts. I soon noticed that, as a consequence, some of those proofs came
out rather longer in print than seemed fair to their often beautifully
simple conception. I would hope, however, that even for the professional
reader the relatively detailed account of those proofs will at least help
to minimize reading time...
If desired, this text can be used for a lecture course with little or
no further preparation. The simplest way to do this would be to follow
the order of presentation, chapter by chapter: apart from two clearly
marked exceptions, any results used in the proof of others precede them
in the text.
Alternatively, a lecturer may wish to divide the material into an easy
basic course for one semester, and a more challenging follow-up course
for another. To help with the preparation of courses deviating from the
order of presentation, I have listed in the margin next to each proof the
reference numbers of those results that are used in that proof. These
references are given in round brackets: for example, a reference (4.1.2)
in the margin next to the proof of Theorem 4.3.2 indicates that Lemma
4.1.2 will be used in this proof. Correspondingly, in the margin next to
Lemma 4.1.2 there is a reference [ 4.3.2 ] (in square brackets) informing
the reader that this lemma will be used in the proof of Theorem 4.3.2.
Note that this system applies between different sections only (of the same
or of different chapters): the sections themselves are written as units and
best read in their order of presentation.
The mathematical prerequisites for this book, as for most graph
theory texts, are minimal: a first grounding in linear algebra is assumed
for Chapter 1.9 and once in Chapter 5.5, some basic topological con-
cepts about the Euclidean plane and 3-space are used in Chapter 4, and
a previous first encounter with elementary probability will help with
Chapter 11. (Even here, all that is assumed formally is the knowledge
of basic definitions: the few probabilistic tools used are developed in the
