Reinhard DiestelGraph TheoryElectronic Edition 2005@ Springer-Verlag Heidelberg, New York 1997, 2000, 2005This is an electronic version of the third (2005)edition of the aboveSpringer book, from their series Graduate Terts in Mathematics, vol. 173.The cross-references in the text and in the margins are active links: clickon them to be taken to the appropriatepage.The printed edition of this book can be ordered viahttp://www.math.uni-hamburg.de/home/diestel/books/graph.theory/where also errata, reviews etc.areposted.Substantial discounts and free copies for lecturers are available for courseadoptions; see here
Reinhard Diestel Graph Theory Electronic Edition 2005 c Springer-Verlag Heidelberg, New York 1997, 2000, 2005 This is an electronic version of the third (2005) edition of the above Springer book, from their series Graduate Texts in Mathematics, vol. 173. The cross-references in the text and in the margins are active links: click on them to be taken to the appropriate page. The printed edition of this book can be ordered via http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ where also errata, reviews etc. are posted. Substantial discounts and free copies for lecturers are available for course adoptions; see here
PrefaceAlmost two decades have passed since the appearance of those graph the-ory texts that still set the agenda for most introductory courses taughttoday.The canon created by those books has helped to identify somemain fields of study and research, and will doubtless continue to influencethe 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, seemingly disparatemethods 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 invari-ants such as average degree 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-decompositions has brought standard methods of surface topologyto bear on long-standing algorithmic graph problemsClearly, then, the time has come for a reappraisal: what are, todaythe essential areas, methods and results that should form the centre ofan introductory graph theory course aiming to equip its audience for 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 havebroken with the tradition of attempting to cover both theory and appli-cations: 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 science as muchas their peers in mathematics: assuming that they prefer algorithms butwill benefit from an encounter with pure mathematics of some kind, 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 conflicting 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
viliPrefaceintroductory text should be lean and concentrate on the essential, so asto 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 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 to make the text enjoyable and easy to read: guidingquestions and ideas will be discussed explicitly, and all proofs presentedwill be rigorous and complete.Atypical 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 (orinterspersed 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 cameout 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 ornofurther preparation.The simplest way to do this would be tofollowthe order of presentation, chapter by chapter: apart from two clearlymarked exceptions, any results used in the proof of others precede themin the textAlternatively,a lecturer may wish to divide the material into an easybasic course for one semester, and a more challenging follow-up coursefor another. To help with the preparation of courses deviating from theorder of presentation, Ihave listed in the margin next to each proof thereference numbers of those results that are used in that proof.Thesereferences 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 Lemma4.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) informingthe 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 sameor of 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 graphtheory texts, are minimal: a first grounding in linear algebra is assumedfor Chapter 1.9 and once in Chapter 5.5, some basic topological con-cepts 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 knowledgeof basic definitions: the few probabilistic tools used are developed in the
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
Prefaceixtext.) There are two areas of graph theory which I find both fascinat.ing and important, especially from the perspective of pure mathematicsadopted here, but which are not covered in this book: these are algebraicgraph theory and infinite graphs.At 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 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 morechallenging ones carry a +. 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 directly below a formal assertion, it means that the proof shouldbe clear after what has been said-a claim waiting to be verified! Thereare also some deeper theorems which are stated, without proof, as back-ground information: these can be identified by the absence of both proofand Almost every book contains errors, and this one will hardly be anexception. I shall try to post on the Web any corrections that becomenecessary. The relevant site may change in time, but will always beaccessible via the following two addresses:http://www.springer-ny.com/supplements/diestel/http://www.springer.de/catalog/html-files/deutsch/math/3540609180.htmlPlease let me know about any errors you find.Little in a textbook is truly original: even the style of writing andof presentation will invariably be influenced by examples. The book thatno doubt influenced me most is the classic GTM graph theory text byBollobas: it was in the course recorded by this text that I learnt 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 time,knowledge and advice in connection with this book. I have benefitedparticularly from the help of N.Alon, G.Brightwell, R. Gillett, R. Halin.M. Hintz, A.Huck, I. Leader, T, Luczak, W. Mader, V, Rodl, A.D.Scott,P.D. Seymour, G.Simonyi, M.Skoviera, R. Thomas, C. Thomassen andP. Valtr. I am 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.March 1997RD
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
xPrefaceAbout the second editionNaturally, I am delighted at having to write this addendum so soon afterthis 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 doneThere are two major changes. The last chapter on graph minorsnow gives a complete proof of one of the major results of the Robertson-Seymour 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 Ithen included ashort proof of the next best thing, the analogous result for path-width.That theorem has now been dropped from Chapter 12. Another additionin this chapter is that the tree-width duality theorem, Theorem 12.3.9,now comes with a (short) proof too.The second major change is the addition of a complete set of hintsfor the exercises. These are largely Tommy Jensen's work, and I amgrateful for 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 beintended for 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 in later proofs) andan ingenious new proof of Menger's theorem 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 Ioffer my special thanks.The Web site for the book has followed me tohttp://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 secondedition by commenting on the firstand Ilook forward to further com-ments!RDDecember 1999
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.3.9, 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