xiiPrefacegraph theorem. However, in all these cases the formal proofs have beenleft essentially untouched.The only substantial change to existing material is that the oldTheorem 8.1.1 (that cr?n edges force a TKr) seems to have lost itsnice (and long) proof. Previously, this proof had served as a welcomeortunitytoexplain methods in sparse extremal graph theory.someThese methods have migrated to the connectivity chapter, where theynow live under theroofof the new proof by Thomas and Wollan that 8knedges make a 2k-connected graphlinked.Sothey arestll there, leanerthan ever before, and just presenting themselves under a new guise. Asa consequence of this change, the two earlier chapters on dense andsparseextremalgraphtheorycouldbereunitedoformanewchapterappropriately named as Eartremal Graph TheoryFinally, there is an entirely new chapter, on infinite graphs. Whengraph theory first emerged as a mathematical discipline, finite and infinite graphsere usually treated on a par. This has changed in recentyears, whichIseeasarerettableloss: infinitegraphs continuetopvide a natural and frequently used bridge to other fields of mathematicsand they hold some special fascination of their own. One aspect of thisis that proofs often have to be more constructive and algorithmic innature than their finite counterparts. The infinite version of Menger'stheorem in Section 8.4 is a typical example: it offers algorithmic insightsinto connectivityproblems networks that are invisible to the slick1inductiveproofsofthefinitetheoremgiveninChapter3.3Oncee more, my thanks go to all the readers and colleagues whosemments helped toimprove the book.Iam particularly grateful to ImreLeader for his judicious comments on the whole of the infinite chapter; tomygraphtheoryseminarnparticularoLilianMatthiesenandPhilippSprissel, for giving the chapter a test run and solving all its exercises(of which eighty survived their scrutiny); to Agelos Georgakopoulos formuch proofreading elsewhere; to Melanie Win Myint for recompiling theindex and extending it substantially:and to Tim Stelldinger for nursingthe whale on page 404 until it was strong enough to carry its babydinosaur.May 2005RDxii Preface graph theorem. However, in all these cases the formal proofs have been left essentially untouched. The only substantial change to existing material is that the old Theorem 8.1.1 (that cr2n edges force a TKr) seems to have lost its nice (and long) proof. Previously, this proof had served as a welcome opportunity to explain some methods in sparse extremal graph theory. These methods have migrated to the connectivity chapter, where they now live under the roof of the new proof by Thomas and Wollan that 8kn edges make a 2k-connected graph k-linked. So they are still there, leaner than ever before, and just presenting themselves under a new guise. As a consequence of this change, the two earlier chapters on dense and sparse extremal graph theory could be reunited, to form a new chapter appropriately named as Extremal Graph Theory. Finally, there is an entirely new chapter, on infinite graphs. When graph theory first emerged as a mathematical discipline, finite and infi- nite graphs were usually treated on a par. This has changed in recent years, which I see as a regrettable loss: infinite graphs continue to pro￾vide a natural and frequently used bridge to other fields of mathematics, and they hold some special fascination of their own. One aspect of this is that proofs often have to be more constructive and algorithmic in nature than their finite counterparts. The infinite version of Menger’s theorem in Section 8.4 is a typical example: it offers algorithmic insights into connectivity problems in networks that are invisible to the slick inductive proofs of the finite theorem given in Chapter 3.3. Once more, my thanks go to all the readers and colleagues whose comments helped to improve the book. I am particularly grateful to Imre Leader for his judicious comments on the whole of the infinite chapter; to my graph theory seminar, in particular to Lilian Matthiesen and Philipp Spr¨ussel, for giving the chapter a test run and solving all its exercises (of which eighty survived their scrutiny); to Agelos Georgakopoulos for much proofreading elsewhere; to Melanie Win Myint for recompiling the index and extending it substantially; and to Tim Stelldinger for nursing the whale on page 404 until it was strong enough to carry its baby dinosaur. May 2005 RD