xiPrefaceAbout the third 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 dfferent things between one pair ofcovers:. areliablefirst introduction to graph theory that can be used eitherfor personal study or as a course text;. a graduate text that offers some depth in selected areas.For each of these aims, some material has been added. Some of thiscovers new topics, 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 stablemarriage theorem in the matching chapter. An example at the graduatelevel 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 theliterature, so that an easily accessiblereferenceseems desirable. Another addition, also in the chapter on graph minors,is a new proof of the‘Kuratowski theorem for higher surfaces'-a proofwhich 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 andalso sheds some more light on the proof of the graph minor theorem.Changes 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 localimprovements are the result of generous feedback I got from colleaguesusing the book in this way, and I am very grateful for their help 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, the proof of the Erdos-Stone theorem now hasan informal post-mortem that looks at how exactly the regularity lemmacomes to be applied in it. Unlike the formal proof, the discussion startsout from the main idea, and finally arrives at how the parameters to 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 perfectgraph theorem. However, in all these cases the formal proofs have beenleft essentially untouched
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 offers some depth in selected areas. 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 graph theorem. However, in all these cases the formal proofs have been left essentially untouched
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 2005RD
xii 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 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 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
ContentsPrefacevii1. The Basics1.1 Graphs*1.2 The degree of a verte1.3Pathsndevele1.4 Connectivity*I1.5 Trees and forests*131.6 Bipartite graphsa1.7 Contraction and minors181.8 Euler tours*21.9.Somelinea21.10 Other notions of graphs2830ExercisesNotes32.Matching, Covering and Packing332.1Matching inbipartitegraphs342.2 Matching in general graphs(*)2.3 Packing and covering .....442.4Tree-packing andarboricity46492.5 Path covers51ExercisesNotes53Sectionsmarkedbyann asterisk are rndedforafirstcOf sectionsmarked (*),thebeginning isrecommended for a first course
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* ....................................... 18 1.8 Euler tours* .................................................... 22 1.9 Some linear algebra ............................................ 23 1.10 Other notions of graphs ........................................ 28 Exercises ....................................................... 30 Notes .......................................................... 32 2. Matching, Covering and Packing ............................. 33 2.1 Matching in bipartite graphs* .................................. 34 2.2 Matching in general graphs(∗) ................................... 39 2.3 Packing and covering ........................................... 44 2.4 Tree-packing and arboricity ..................................... 46 2.5 Path covers .................................................... 49 Exercises ....................................................... 51 Notes .......................................................... 53 * Sections marked by an asterisk are recommended for a first course. Of sections marked (∗), the beginning is recommended for a first course
xivContents3.Connectivity553.1 2-Connected graphs and subgraphs553.2The structureof 3-connectedgrapl83.3 Menger's theorem3.4 Mader's theo673.5Linking pairs of vertices69ExercisesNotes804. Planar Graphs4.1 Topological prerequisito4.2Plane graphs864.3Drawing924.4Planar gra96sKurato1014.5Algebraic planarityrcriter4.6Plane duality103Exercises106Notes1095. Colouring ..1115.1 Colouring maps and planar graphs*1125.2 Colouring vertices*1145.3 Colouring edge1195.4 List colouring1215.5Perfectgraphs126133ExercisesA+Notes1366. Flows1396.1 Circulations(*)1401416.2 Flows in networ6.3Group-valued flows1446.4k-Flowsforsmallk1491526.5 Flow-colouringduali6.6 Tutte's flow conjectures156160ExercisesNotes.*161
xiv Contents 3. Connectivity .................................................... 55 3.1 2-Connected graphs and subgraphs* ............................ 55 3.2 The structure of 3-connected graphs(∗) .......................... 57 3.3 Menger’s theorem* ............................................. 62 3.4 Mader’s theorem ............................................... 67 3.5 Linking pairs of vertices(∗) ...................................... 69 Exercises ....................................................... 78 Notes .......................................................... 80 4. Planar Graphs .................................................. 83 4.1 Topological prerequisites* ...................................... 84 4.2 Plane graphs* .................................................. 86 4.3 Drawings ....................................................... 92 4.4 Planar graphs: Kuratowski’s theorem* .......................... 96 4.5 Algebraic planarity criteria ..................................... 101 4.6 Plane duality ................................................... 103 Exercises ....................................................... 106 Notes .......................................................... 109 5. Colouring ........................................................ 111 5.1 Colouring maps and planar graphs* ............................. 112 5.2 Colouring vertices* ............................................. 114 5.3 Colouring edges* ............................................... 119 5.4 List colouring .................................................. 121 5.5 Perfect graphs .................................................. 126 Exercises ....................................................... 133 Notes .......................................................... 136 6. Flows ............................................................ 139 6.1 Circulations(∗) .................................................. 140 6.2 Flows in networks* ............................................. 141 6.3 Group-valued flows ............................................. 144 6.4 k-Flows for small k ............................................. 149 6.5 Flow-colouring duality .......................................... 152 6.6 Tutte’s flow conjectures ........................................ 156 Exercises ....................................................... 160 Notes .......................................................... 161
ContentsXV7. Extremal Graph Theory1637.1 Subgraphs*1647.2 Minors(*).1697.3 Hadwiger's conjecturei.1727.4 Szemeredi's regularity lemm1751837.5 Applying the regularity le189ExercisesNotes1928.Infinite Graphs.1958.1 Basic notions, facts and techniques1968.2 Paths, trees, and ends(*)2042128.3Homogeneus and universal grap2168.4Connectivityndmatching8.5 The topological end space226Exercises237Notes2449. Ramsey Theory for Graphs2512529.1 Ramsey's original theorems9.2 Ramsey numbers(*)2559.3InducedRamsey theorems2589.4 Ramsey properties and connectivity(*).268Exercises271Notes27210. Hamilton Cycles27510.1Simplesufficientconditions27510.2 Hamilton cycles and degree sequences27828110.3Hamilton cycles in the square of a graphExercises289Notes290
Contents xv 7. Extremal Graph Theory ....................................... 163 7.1 Subgraphs* .................................................... 164 7.2 Minors(∗) ....................................................... 169 7.3 Hadwiger’s conjecture* ......................................... 172 7.4 Szemer´edi’s regularity lemma ................................... 175 7.5 Applying the regularity lemma ................................. 183 Exercises ....................................................... 189 Notes .......................................................... 192 8. Infinite Graphs ................................................. 195 8.1 Basic notions, facts and techniques* ............................ 196 8.2 Paths, trees, and ends(∗) ........................................ 204 8.3 Homogeneous and universal graphs* ............................ 212 8.4 Connectivity and matching ..................................... 216 8.5 The topological end space ...................................... 226 Exercises ....................................................... 237 Notes .......................................................... 244 9. Ramsey Theory for Graphs ................................... 251 9.1 Ramsey’s original theorems* .................................... 252 9.2 Ramsey numbers(∗) ............................................. 255 9.3 Induced Ramsey theorems ...................................... 258 9.4 Ramsey properties and connectivity(∗) ........................... 268 Exercises ....................................................... 271 Notes .......................................................... 272 10. Hamilton Cycles .............................................. 275 10.1 Simple sufficient conditions* .................................... 275 10.2 Hamilton cycles and degree sequences* ......................... 278 10.3 Hamilton cycles in the square of a graph ........................ 281 Exercises ....................................................... 289 Notes .......................................................... 290