xiiPrefaceThe only substantial change to existing material is that the oldTheorem 8.1.1 (that crn edges force a TK') seems to have lost itsnice (and long) proof. Previously, this proof had served as a welcomeopportunity to explain some methods in sparse extremal graph theory.These methods have migrated to the connectivity chapter, where theynow live under the roof of the new proof by Thomas and Wollan that 8knedges make a 2k-connected graph k-linked. So they are stillthere, leanerthan ever before, and just presenting themselves under a new guise. Asa consequence of this change, the two earlier chapters on dense andsparse extremal graph theory could be reunited, to form a new chapterappropriately named as Ertremal Graph Theory.Finally, there is an entirely new chapter, on infinite graphs. Whengraph theory first emerged as a mathematical discipline, finite and infi-nite graphs were usually treated on a par. This has changed in recentyears,which II 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 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 connectivity problems in networks that are invisible to the slickinductive proofs of the finite theorem given in Chapter 3.3.Once more, my thanks go to all the readers and colleagues whosecomments helped to improve the book. I am particularly grateful to ImreLeader for his judicious comments on the whole of the infinite chapter; tomy graph theory seminar, in particular to Lilian Matthiesen and PhilippSprissel, for giving the chapter a test run and solving all its exercises(of which eighty survived their scrutiny); to Angelos Georgakopoulos formuch proofreading elsewhere; to Melanie Win Myint for recompiling theindex and extending it substantially; and to Tim Stelldinger for nursingthe whale on page 366 until it was strong enough to carry its babydinosaur.May 2005RDxii Preface 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 Angelos 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 366 until it was strong enough to carry its baby dinosaur. May 2005 RD