PrefacexiAboutthethird 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 different things between one pairofcovers:areliablefrst introduction tographtheory thatcan beused eitherfor personal study or as a course text;duate text that also offers some depth on thamaimportantopics.For each of these aims, some material has been added. Some of thiscoversnetopics,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 stable in the matching chapter. An example at the graduategethlevel 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 the literature, so that an easily accessible referenceseems desirable. Another addition, also in the chapter on graph mis a new proof of the Kuratowski theorem for higher surfaces-aproofwhich 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 andnore light on the proof of the graph minor theoremalsoshesomeChanges 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 localimprovementsare the result of generousfeedbackIgot from colleagueusing thebook in this way,andIam verygratefulforthirhelp 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,theproof of theErdos-Stonetheorem nowhasininformal post-mortemthatlooksathowexactlytheregularitylemmcomes to be applied in it. Unlike the formal proof, the discussion startsoutfromthemain idea,andfinallyarrives athowtheparametersto 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 perfecPreface 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 also offers some depth on the most important topics. 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