Graduate Texts in MathematicsGTMReinhard DiestelGraph TheoryFifthEdition Springer
Graduate Texts in Mathematics Graph Theory Reinhard Diestel Fifth Edition
PrefaceAlmost twodecadeshave passed sincethe appearance of thosegraphtheory texts that still set the agenda for most introductory courses taughttodayThecanon created bythosebookshashelped toidentifysomen fields of study and research, and will doubtless continue to influence9the development of the discipline for some time to comeYet much has happened in those 20 years, in graph theory no lessthan elsewhere: deep new theorems have been found, seenlinglydisparatemethods and results have become interrelated, entire new branches havearisen. To name just a few such developments, one may think of howthe new notion of list colouring has bridged the gulf between invariants such as avedegree and chromatic number, how probabilisticmethods and the regularity lemma have pervaded extremal graph theoryand Ramsey theory, or how the entirely new field of graph minors andtree-decositionshasbrought standard methodsofsurfacetopologyto bear on long-standing algorithmic graph problems.Clearly,then,thetimehas comeforareappraisalwhat are,todaythessential areas, methods and results that should form the centre ofanintroductorygraphtheory courseaiming toequipits audiencefor themost likely developments ahead?I have tried in this book to offer material for such a course. Inview of the increasing complexity and maturity of the subject, I havebrokenwiththetraditionofattemptingtocoverboththeoryand applications: this book offers an introduction to the theory of graphs as partof (pure) mathematics; it contains neither explicit algorithms nor 'realworld' applications. My hope is that the potential for depth gained bythis restriction in scope will serve students of computer science8Smucas their peers in mathematics: assuming that they prefer algorithms butwillbenefitfromanencounterwithpuremathematicsofsomekind,itseems an ideal opportunity to look for this close to where their heart lies!In the selection and presentation of material, I have tried to ac-commodate two conficting goals. On the one hand, I believe that an
Preface Almost two decades have passed since the appearance of those graph theory texts that still set the agenda for most introductory courses taught today. The canon created by those books has helped to identify some main fields of study and research, and will doubtless continue to influence the development of the discipline for some time to come. Yet much has happened in those 20 years, in graph theory no less than elsewhere: deep new theorems have been found, seemingly disparate methods and results have become interrelated, entire new branches have arisen. To name just a few such developments, one may think of how the new notion of list colouring has bridged the gulf between invariants such as average degree and chromatic number, how probabilistic methods and the regularity lemma have pervaded extremal graph theory and Ramsey theory, or how the entirely new field of graph minors and tree-decompositions has brought standard methods of surface topology to bear on long-standing algorithmic graph problems. Clearly, then, the time has come for a reappraisal: what are, today, the essential areas, methods and results that should form the centre of an introductory graph theory course aiming to equip its audience for the most likely developments ahead? I have tried in this book to offer material for such a course. In view of the increasing complexity and maturity of the subject, I have broken with the tradition of attempting to cover both theory and applications: this book offers an introduction to the theory of graphs as part of (pure) mathematics; it contains neither explicit algorithms nor ‘real world’ applications. My hope is that the potential for depth gained by this restriction in scope will serve students of computer science as much as their peers in mathematics: assuming that they prefer algorithms but will benefit from an encounter with pure mathematics of some kind, it seems an ideal opportunity to look for this close to where their heart lies! In the selection and presentation of material, I have tried to accommodate two conflicting goals. On the one hand, I believe that an
viiPrefaceintroductory text should be lean and concentrate on the essential, so asto offer guidance to those new to the field. As a graduate text, moreoverit should get to the heart of the matter quickly:after all, the idea is toconvey at least an impression of the depth and methods of the subject.On the other hand, it has been my particular concern to write withsufficient detail tomake the text enjoyable and easy to read: guidingquestions and ideas will be discussed explicitly, and all proofs presentedwill be rigorous and complete.A typical chapter, therefore, begins with a brief discussion of whatare the guiding questions in the area it covers, continues with a succinctaccount of its classic results (often with simplified proofs),and thenpresents one or two deeper theorems that bring out the full flavour ofthat area. The proofs of these latter results are typically preceded by (orinterspesed with) an informal account of their main ideas, but are thenpresented formally at the same level of detail as their simpler counterparts. I soon noticed that, as a consequence, some of those proofs camout rather longer in print than seemed fair to their often beautifullysimple conception. I would hope, however, that even for the professionalreader the relatively detailed account of those proofs will at least helpto minimize reading time.If desired, this text can be used for a lecture course with little orno further preparation. The simplest way to do this would be to followthe order of presentation, chapter by chapter:apart from two clearlymarked exceptions, any results used in the proof of others precede themin the text.Alternatively,a lecturermaywishtodividethematerial into an easybasic course for oneester,and a more challengingfollow-up coursefor anotherTohelpwiththepreparation of courses deviatingfrom theorderofprentation,I have listed in themargin next to each proof thereferennumbersofthoseresults that are used in that proof. TheserefereI round brackets: for example, a reference (4.1.2)saregiven inext to the proof of Theorem 4.3.2 indicates that Lemmanthe:4.1.2 will be used in this proof. Correspondingly, in the margin next toLemma 4.1.2 there is a reference [4.3.2] (in square brackets) informing thereader that this lemma will be used in the proof of Theorem 4.3.2. Notethat this system applies between different sections only (of the same orof different chapters):the sections themselves are written as units andbest read in their order of presentation.The mathematical prerequisites for this book, as for most graphimal: a first grounding in linear algebra is assexts.for Chapter 1.9 and once in Chapter 5.5, some basic topological concepts about the Euclidean plane and 3-space are used in Chapter 4, anda previous first encounter with elementary probability will help withChapter 1l. (Even here, all that is assumed formally is the knowledgeofbasic definitions:thefewprobabilistictoolsused aredeveloped inthe
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. A typical 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 counterparts. 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 concepts 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
Prefaceixof graph theory which I find both fascinatext.)Thering and important, especially from the perspective of pure mathematicsadopted here, but which are not covered in this book: these are algebraicgraph theory and infinite graphsAt the end of each chapter, there is a section with exercises andanother with bibliographical and historical notes. Many of the exerciseswere chosen to complement the main narrative of the text: they illus-trate newconcepts,showhowa new invariantrelates to earlier ones,indicate ways in which a result stated in the text is best possibleParticularly easy exercises are identified by the superscriptthe morechallenging ones carry a t. The notes are intended to guide the readeron to further reading, in particular to any monographs or survey articleson the theme of that chapter.They also offer some historical and otherremarks on the material presented in the text.Ends of proofs are marked by the symbol . Where this symbol isfound directlybelowa formal assertion, it means thatthe proof shouldbe clear after what has been said-a claim waiting to be verified! Thereare alsce deeper theorems which are stated, without proof, as back.ground informationthese canbeidentifiedbytheabsenceofboth proofandAlmost every book contains errors, and this one willhardly be anexception. I shall try to post on the Web any corrections that become The relevant site may change in time, but will always beleceaccessible via the following two addresseshttp://www.springer-ny.com/supplements/diestel/w.springer.de/catalog/html-files/deutsch/math/3540609180.htmlhttp://wtPlease let me know about anyy errors you find.Little in a textbook is truly original: even the style of writing andof presentation will invariably be influenced bycamples. The book thatoubt influenced me most is the classic GTM graph theory text byBollobas: it was in the course recorded by this text that Ilearnt my firstgraph theory as a student. Anyone who knows this book well will feelits influence here, despite all differences in contents and presentationI should like to thank all who gave so generously of their timeknowledge and advice in connection with this book. I have benefitedDarticularly from thehelp of N.Alon, G.Brightwell,R.Gillett,R.Halin.M. Hintz, A. Huck, I. Leader.T.Luczak.W.Mader.V.Rodl.A.D.ScottP.D.Seymour, G.Simonyi, M. Skoviera, R.Thomas, C. Thomassen andP Valtr. Iam particularly grateful also to Tommy R.Jensen, who taughtme much about colouring and all I know about k-flows, and who investedimmense amounts of diligence and energy in his proofreading of the pre-liminary German version of this book.RDMarch 1997
Preface ix text.) There are two areas of graph theory which I find both fascinating and important, especially from the perspective of pure mathematics adopted here, but which are not covered in this book: these are algebraic graph theory and infinite graphs. At the end of each chapter, there is a section with exercises and another with bibliographical and historical notes. Many of the exercises were chosen to complement the main narrative of the text: they illustrate new concepts, show how a new invariant relates to earlier ones, or indicate ways in which a result stated in the text is best possible. Particularly easy exercises are identified by the superscript −, the more challenging ones carry a +. The notes are intended to guide the reader on to further reading, in particular to any monographs or survey articles on the theme of that chapter. They also offer some historical and other remarks on the material presented in the text. Ends of proofs are marked by the symbol . Where this symbol is found directly below a formal assertion, it means that the proof should be clear after what has been said—a claim waiting to be verified! There are also some deeper theorems which are stated, without proof, as background information: these can be identified by the absence of both proof and . Almost every book contains errors, and this one will hardly be an exception. I shall try to post on the Web any corrections that become necessary. The relevant site may change in time, but will always be accessible via the following two addresses: http://www.springer-ny.com/supplements/diestel/ http://www.springer.de/catalog/html-files/deutsch/math/3540609180.html Please let me know about any errors you find. Little in a textbook is truly original: even the style of writing and of presentation will invariably be influenced by examples. The book that no doubt influenced me most is the classic GTM graph theory text by Bollob´as: it was in the course recorded by this text that I learnt my first graph theory as a student. Anyone who knows this book well will feel its influence here, despite all differences in contents and presentation. I should like to thank all who gave so generously of their time, knowledge and advice in connection with this book. I have benefited particularly from the help of N. Alon, G. Brightwell, R. Gillett, R. Halin, M. Hintz, A. Huck, I. Leader, T. Luczak, W. Mader, V. R¨odl, A.D. Scott, P.D. Seymour, G. Simonyi, M. Skoviera, R. Thomas, C. Thomassen and ˇ P. Valtr. I am particularly grateful also to Tommy R. Jensen, who taught me much about colouring and all I know about k-flows, and who invested immense amounts of diligence and energy in his proofreading of the preliminary German version of this book. March 1997 RD
PrefaceAboutthesecondeditionNaturally, Iam delighted at havingto write this addendumsosoonaferthis book came out in the summer of 1997. It is particularly gratifyingto hear that people are gradually adopting it not only for their personaluse but more and more also as a course text; this, after all, was my aimwhen I wrote it, and my excuse for agonizing more over presentationthan I might otherwise have done.The last chapter on graphThere are two major changesminorsnow gives a complete proof of one of the major results of the RobertsonSeymour theory, their theorem that excluding a graph as a minor boundsthe tree-width if and only if that graph is planar. This short proof didnot exist when I wrote the first edition, which is why I then included ashortproof of the next best thing.the analogous result for path-width.That theorem hasn dropped from Chapter 12. Another additionin this chapter is that the tree-width duality theorem, Theorem 12.4.3,with a (short) proof tocnowcomThe secondmajor change is theaddition ofacompleteset ofhintsfor the exercises. These are largely Tommy Jensen's work, and I amgratefulfor the time he donated to this project.The aim of these hintsis to help those who use the book to study graph theory on their own,but not to spoil the fun. The exercises, including hints, continue to beintendedfor classroom useApart from these two changes, there are a few additions. The mostnoticable of these are the formal introduction of depth-first search treesin Section 1.5 (which has led to some simplifications irin later proofs) andan ingenious new proof of Menger'stheorem due to Bohme, Goring andHarant (which has not otherwise been published).Finally, there is a host of small simplifications and clarificationsof arguments that I noticed as I taught from the book, or which werepointed out to me by others. To all these I offer my special thanks.The Web site for the book has followed me tohttp:/www.math.uni-hamburg.de/home/diestel/books/graph.theory/Iexpect this address to be stable for some timeOnce more, my thanks go to all who contributed to this secondedition by commenting on the frstandIlook forward tofurther comments!December 1999RD
x Preface About the second edition Naturally, I am delighted at having to write this addendum so soon after this book came out in the summer of 1997. It is particularly gratifying to hear that people are gradually adopting it not only for their personal use but more and more also as a course text; this, after all, was my aim when I wrote it, and my excuse for agonizing more over presentation than I might otherwise have done. There are two major changes. The last chapter on graph minors now gives a complete proof of one of the major results of the RobertsonSeymour theory, their theorem that excluding a graph as a minor bounds the tree-width if and only if that graph is planar. This short proof did not exist when I wrote the first edition, which is why I then included a short proof of the next best thing, the analogous result for path-width. That theorem has now been dropped from Chapter 12. Another addition in this chapter is that the tree-width duality theorem, Theorem 12.4.3, now comes with a (short) proof too. The second major change is the addition of a complete set of hints for the exercises. These are largely Tommy Jensen’s work, and I am grateful for the time he donated to this project. The aim of these hints is to help those who use the book to study graph theory on their own, but not to spoil the fun. The exercises, including hints, continue to be intended for classroom use. Apart from these two changes, there are a few additions. The most noticable of these are the formal introduction of depth-first search trees in Section 1.5 (which has led to some simplifications in later proofs) and an ingenious new proof of Menger’s theorem due to B¨ohme, G¨oring and Harant (which has not otherwise been published). Finally, there is a host of small simplifications and clarifications of arguments that I noticed as I taught from the book, or which were pointed out to me by others. To all these I offer my special thanks. The Web site for the book has followed me to http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ I expect this address to be stable for some time. Once more, my thanks go to all who contributed to this second edition by commenting on the first—and I look forward to further comments! December 1999 RD
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 perfec
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 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 increasingly 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
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 2005RD
xii 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 provide 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
xiiPrefaceAboutthefourtheditionIn this fourth edition there are few substantial additions of new material, but many improvements.As with previous new editions, there are countless small and subtlechanges to further elucidate a particular argument or concept. Whenprompted by reader feedback, for which I am always grateful, I still tryto recast details that have been found harder than they should be. Thesecan be very basic; a nice example, this time, is the definition of a minorin ChapterAtamoresubostantiallevel.thereralnewandsimareseyDlerproof classical results, in one case reducing the already shortened earlierproof to halfits length (and twice its beauty),These newly added proofsinclude the marriage theorem, the tree packing theorem, Tutte's cyclespace and wheel theorem, Fleischner's theorem on Hamilton cycles, andthe threshold theorem for the edge probability guaranteeing a specifiedtype of subgraph.Thereare also one or two genuinely new theoremsOne of theseious local degree cconditionfortheexistenceofaisaninHamilton cycle, due to Asratian and Khachatrian, that implies a numberof classicalnicity theoremsIn some sections I have reorganized the material slightly, or rewrten the narrative. Typically, these are sections that had grown over theprevious three editions, and this was beginning to affect their balanceof material and momentum. As the book remains committed to offeringnot just a collection of theorems and proofs, but tries whenever possibleto indicate a somewhat larger picture in which these have their placemaintaining its original freshness and flow remains a challenge that Ienjoy trying to meet.Finally, the book has its own dedicated website now, athttp://diestel-graph-theory.com/Potentially, this offers opportunities for more features surrounding thebookthan thetraditional free online edition and adwindling collectionofmisprints.Ifyouhaveanyideasand wouldliketoseethemimplementeddo let me know.RDMay 2010
Preface xiii About the fourth edition In this fourth edition there are few substantial additions of new material, but many improvements. As with previous new editions, there are countless small and subtle changes to further elucidate a particular argument or concept. When prompted by reader feedback, for which I am always grateful, I still try to recast details that have been found harder than they should be. These can be very basic; a nice example, this time, is the definition of a minor in Chapter 1. At a more substantial level, there are several new and simpler proofs of classical results, in one case reducing the already shortened earlier proof to half its length (and twice its beauty). These newly added proofs include the marriage theorem, the tree packing theorem, Tutte’s cycle space and wheel theorem, Fleischner’s theorem on Hamilton cycles, and the threshold theorem for the edge probability guaranteeing a specified type of subgraph. There are also one or two genuinely new theorems. One of these is an ingenious local degree condition for the existence of a Hamilton cycle, due to Asratian and Khachatrian, that implies a number of classical hamiltonicity theorems. In some sections I have reorganized the material slightly, or rewritten the narrative. Typically, these are sections that had grown over the previous three editions, and this was beginning to affect their balance of material and momentum. As the book remains committed to offering not just a collection of theorems and proofs, but tries whenever possible to indicate a somewhat larger picture in which these have their place, maintaining its original freshness and flow remains a challenge that I enjoy trying to meet. Finally, the book has its own dedicated website now, at http://diestel-graph-theory.com/ Potentially, this offers opportunities for more features surrounding the book than the traditional free online edition and a dwindling collection of misprints. If you have any ideas and would like to see them implemented, do let me know. May 2010 RD
xivPrefaceAboutthefiftheditionThis ffth edition of thee book is again a major overhaul, in the spirit ofits first and third edition.I have rewritten Chapter 12 on graph minors to take account ofrecent developments.In addition to many smaller updates it offersnew proof ofthetree-width duality theorem.duetoMazoit.whichhas not otherwise been published. More fundamentally.I have addeda sectionDntangles.OriginallydevisedbyRobertsonandSeymourasal device for their proof of the graphrti1,tangleshave turned out to beamental than this: they defirnoa new paradigm for identifying highly connected parts in a graph. Un-like earlier attempts at defining such substructuresin terms of, sayhighly connected subgraphs, minors, or topological minotanglesdonot attempt to pin down this substructure in terms of vertices, edges, orconnecting paths,but seek to captureit indirectly by orienting all thelow-order separations of the graph towards itIn short.we no longer askwhat exactly the highly connected region is.but only where it is.Fors, this is exactly what matters. Moreoover.thismabstonofhighlocalconnectivity can eorted toSVDecontexts outside graph theory. This, in turn, makes graph minoseorapplicable beyond graph theory itself in a new way, via tangles. I havewritten the new section on tangles from this modern perspective.Chapter 2hasanewlywritten section on tree packand coveringI rewrote it from scratch to take advantage of a beautiful new unifiedtheorem containbothaspectsatonce:thepacking-coveringtheoremof BowlerandCarmesin.Whiletheiroriginal result wasproved formtroids, its graph version hasavery shortand self-contained proof.Thisn in Chapter 2.4, and again is not fproof is givend in print elsewheChapter 8, on infinitegraphs, now treats the topological aspects oflocally finite graphs more thoroughly. It puts the Freudenthal compactification of a graph G into perspective by describing it, in addition, asinverse limit of the finite contractionnors of G.Readers withbackground in group theory will find this familiar.Asalways,thereare countless small improvementstothenarrativeand exercises. My thanksgo to all those who suggested thesDroofsFinally, I have made two adjustments to help ensure that the ex.sahleinataimeofinstaTheHints appendix still exists, but has been relegated to the professionalelectronic edition so that lecturers can decide which hints to give andwhich not. Similarly, exercises asking for a proof of a named theorem nolonger mention this name, so that the proof cannot simply be searchedfor. However if you know the name and wish to find the exercise, theindex still has a name entry that will take you to the right pageRDJuly 2016
xiv Preface About the fifth edition This fifth edition of the book is again a major overhaul, in the spirit of its first and third edition. I have rewritten Chapter 12 on graph minors to take account of recent developments. In addition to many smaller updates it offers a new proof of the tree-width duality theorem, due to Mazoit, which has not otherwise been published. More fundamentally, I have added a section on tangles. Originally devised by Robertson and Seymour as a technical device for their proof of the graph minor theorem, tangles have turned out to be much more fundamental than this: they define a new paradigm for identifying highly connected parts in a graph. Unlike earlier attempts at defining such substructures—in terms of, say, highly connected subgraphs, minors, or topological minors—tangles do not attempt to pin down this substructure in terms of vertices, edges, or connecting paths, but seek to capture it indirectly by orienting all the low-order separations of the graph towards it. In short, we no longer ask what exactly the highly connected region is, but only where it is. For many applications, this is exactly what matters. Moreover, this more abstract notion of high local connectivity can easily be transported to contexts outside graph theory. This, in turn, makes graph minor theory applicable beyond graph theory itself in a new way, via tangles. I have written the new section on tangles from this modern perspective. Chapter 2 has a newly written section on tree packing and covering. I rewrote it from scratch to take advantage of a beautiful new unified theorem containing both aspects at once: the packing-covering theorem of Bowler and Carmesin. While their original result was proved for matroids, its graph version has a very short and self-contained proof. This proof is given in Chapter 2.4, and again is not found in print elsewhere. Chapter 8, on infinite graphs, now treats the topological aspects of locally finite graphs more thoroughly. It puts the Freudenthal compactification of a graph G into perspective by describing it, in addition, as an inverse limit of the finite contraction minors of G. Readers with a background in group theory will find this familiar. As always, there are countless small improvements to the narrative, proofs, and exercises. My thanks go to all those who suggested these. Finally, I have made two adjustments to help ensure that the exercises remain usable in class at a time of instant internet access. The Hints appendix still exists, but has been relegated to the professional electronic edition so that lecturers can decide which hints to give and which not. Similarly, exercises asking for a proof of a named theorem no longer mention this name, so that the proof cannot simply be searched for. However if you know the name and wish to find the exercise, the index still has a name entry that will take you to the right page. July 2016 RD
ContentsDrefaceVI1. The Basics1.1 Graphs*1.2 The degree ofL1.3 Paths and cycles*1.4Connectivity10131.5 TreesO441.6 Bipartite graphs*117-1.8 Euler tours*a231.9SorJinearalo1.10 Other27notionsofgraphsExercises30Note2. Matching, Covering and Packing352.1 Matching in bipartite graphs*362.2 Matching in general graphs(412.3 The Erd&s-P6sa theorem452.4 Tree packing and arboricity522.5 Path covers+++++++++++Exercises53SectionsmaarerecommendedfoOf.ionemarthelxinninmencedfohrst
Contents Preface ................................................................ vii 1. The Basics ...................................................... 1 1.1 Graphs* ........................................................ 2 1.2 The degree of a vertex* ......................................... 5 1.3 Paths and cycles* .............................................. 6 1.4 Connectivity* .................................................. 10 1.5 Trees and forests* .............................................. 13 1.6 Bipartite graphs* ............................................... 17 1.7 Contraction and minors* ....................................... 19 1.8 Euler tours* .................................................... 22 1.9 Some linear algebra ............................................ 23 1.10 Other notions of graphs ........................................ 27 Exercises ....................................................... 30 Notes .......................................................... 33 2. Matching, Covering and Packing ............................. 35 2.1 Matching in bipartite graphs* .................................. 36 2.2 Matching in general graphs(∗) ................................... 41 2.3 The Erd˝os-P´osa theorem ....................................... 45 2.4 Tree packing and arboricity ..................................... 48 2.5 Path covers .................................................... 52 Exercises ....................................................... 53 Notes .......................................................... 56 * Sections marked by an asterisk are recommended for a first course. Of sections marked (∗), the beginning is recommended for a first course