xiPrefaceAbout the third editionThere is no denying that this book has grown. Is it still as 'lean andconcentrating on the essential' as I said it should be when I wrote thepreface to the first edition, now almost eight years ago?Ibelieve that it is, perhaps now more than ever. So why the increasein volume? Part of the answer is that I have continued to pursue theoriginal dual aim of offering two dfferent things between one pair ofcovers:. areliablefirst introduction to graph theory that can be used eitherfor personal study or as a course text;. a graduate text that offers some depth in selected areas.For each of these aims, some material has been added. Some of thiscovers new topics, which can be included or skipped as desired.Anexample at the introductory level is the new section on packing andcovering with the Erdos-Posa theorem, or the inclusion of the stablemarriage theorem in the matching chapter. An example at the graduatelevel is the Robertson-Seymour structure theorem for graphs without agiven minor:a result that takes a few lines to state, but one which is in-creasingly relied on in theliterature, so that an easily accessiblereferenceseems desirable. Another addition, also in the chapter on graph minors,is a new proof of the‘Kuratowski theorem for higher surfaces'-a proofwhich illustrates the interplay between graph minor theory and surfacetopology better than was previously possible. The proof is complementedby an appendix on surfaces, which supplies the required background andalso sheds some more light on the proof of the graph minor theorem.Changes that affect previously existing material are rare, except forcountless local improvements intended to consolidate and polish ratherthan change. I am aware that, as this book is increasingly adopted asa course text, there is a certain desire for stability. Many of these localimprovements are the result of generous feedback I got from colleaguesusing the book in this way, and I am very grateful for their help andadviceThere are also some local additions. Most of these developed frommy own notes, pencilled in the margin as I prepared to teach from thebook. They typically complement an important but technical proof,when I felt that its essential ideas might get overlooked in the formalwrite-up. For example, the proof of the Erdos-Stone theorem now hasan informal post-mortem that looks at how exactly the regularity lemmacomes to be applied in it. Unlike the formal proof, the discussion startsout from the main idea, and finally arrives at how the parameters to bedeclared at the start of the formal proof must be specified. Similarlythere is now a discussion pointing to some ideas in the proof of the perfectgraph theorem. However, in all these cases the formal proofs have beenleft essentially untouched.Preface xi About the third edition There is no denying that this book has grown. Is it still as ‘lean and concentrating on the essential’ as I said it should be when I wrote the preface to the first edition, now almost eight years ago? I believe that it is, perhaps now more than ever. So why the increase in volume? Part of the answer is that I have continued to pursue the original dual aim of offering two different things between one pair of covers: • a reliable first introduction to graph theory that can be used either for personal study or as a course text; • a graduate text that offers some depth in selected areas. For each of these aims, some material has been added. Some of this covers new topics, which can be included or skipped as desired. An example at the introductory level is the new section on packing and covering with the Erd˝os-P´osa theorem, or the inclusion of the stable marriage theorem in the matching chapter. An example at the graduate level is the Robertson-Seymour structure theorem for graphs without a given minor: a result that takes a few lines to state, but one which is in￾creasingly relied on in the literature, so that an easily accessible reference seems desirable. Another addition, also in the chapter on graph minors, is a new proof of the ‘Kuratowski theorem for higher surfaces’—a proof which illustrates the interplay between graph minor theory and surface topology better than was previously possible. The proof is complemented by an appendix on surfaces, which supplies the required background and also sheds some more light on the proof of the graph minor theorem. Changes that affect previously existing material are rare, except for countless local improvements intended to consolidate and polish rather than change. I am aware that, as this book is increasingly adopted as a course text, there is a certain desire for stability. Many of these local improvements are the result of generous feedback I got from colleagues using the book in this way, and I am very grateful for their help and advice. There are also some local additions. Most of these developed from my own notes, pencilled in the margin as I prepared to teach from the book. They typically complement an important but technical proof, when I felt that its essential ideas might get overlooked in the formal write-up. For example, the proof of the Erd˝os-Stone theorem now has an informal post-mortem that looks at how exactly the regularity lemma comes to be applied in it. Unlike the formal proof, the discussion starts out from the main idea, and finally arrives at how the parameters to be declared at the start of the formal proof must be specified. Similarly, there is now a discussion pointing to some ideas in the proof of the perfect graph theorem. However, in all these cases the formal proofs have been left essentially untouched