244 Graduate Texts in Mathematics EditorialBoard S.Axler K.A.Ribet GraduateTextsinMathematics 1 TAKEUTI/ZARING.IntroductiontoAxiomatic 38 GRAUERT/FRITZSCHE.SeveralComplex SetTheory.2nded. Variables. 2 OXTOBY.MeasureandCategory.2nded. 39 ARVESON.AnInvitationtoC-Algebras. 3 SCHAEFER.TopologicalVectorSpaces.2nded. 40 KEMENY/SNELL/KNAPP.DenumerableMarkov 4 HILTON/STAMMBACH.ACoursein Chains.2nded. HomologicalAlgebra.2nded. 41 APOSTOL.ModularFunctionsandDirichlet 5 MACLANE.CategoriesfortheWorking SeriesinNumberTheory.2nded. Mathematician.2nded. 42 J.-P.SERRE.LinearRepresentationsofFinite 6 HUGHES/PIPER.ProjectivePlanes. Groups. 7 J.-P.Serre.ACourseinArithmetic. 43 GILLMAN/JERISON.RingsofContinuous 8 TAKEUTI/ZARING.AxiomaticSetTheory. Functions. 9 HUMPHREYS.IntroductiontoLieAlgebrasand 44 KENDIG.ElementaryAlgebraicGeometry. RepresentationTheory. 45 LOE`ve.ProbabilityTheoryI.4thed. 10 COHEN.ACourseinSimpleHomotopyTheory. 46 LOE`ve.ProbabilityTheoryII.4thed. 11 CONWAY.FunctionsofOneComplex 47 MOISE.GeometricTopologyinDimensions VariableI.2nded. 2and3. 12 BEALS.AdvancedMathematicalAnalysis. 48 SACHS/WU.GeneralRelativityfor 13 ANDERSON/FULLER.RingsandCategoriesof Mathematicians. Modules.2nded. 49 GRUENBERG/WEIR.LinearGeometry. 14 GOLUBITSKY/GUILLEMIN.StableMappings 2nded. andTheirSingularities. 50 EDWARDS.Fermat’sLastTheorem. 15 BERBERIAN.LecturesinFunctionalAnalysis 51 KLINGENBERG.ACourseinDifferential andOperatorTheory. Geometry. 16 WINTER.TheStructureofFields. 52 HARTSHORNE.AlgebraicGeometry. 17 ROSENBLATT.RandomProcesses.2nded. 53 MANIN.ACourseinMathematicalLogic. 18 HALMOS.MeasureTheory. 54 GRAVER/WATKINS.Combinatoricswith 19 HALMOS.AHilbertSpaceProblemBook. EmphasisontheTheoryofGraphs. 2nded. 55 BROWN/PEARCY.IntroductiontoOperator 20 HUSEMOLLER.FibreBundles.3rded. TheoryI:ElementsofFunctionalAnalysis. 21 HUMPHREYS.LinearAlgebraicGroups. 56 MASSEY.AlgebraicTopology:AnIntroduction. 22 BARNES/MACK.AnAlgebraicIntroductionto 57 CROWELL/FOX.IntroductiontoKnotTheory. MathematicalLogic. 58 KOBLITZ.p-adicNumbers,p-adicAnalysis, 23 GREUB.LinearAlgebra.4thed. andZeta-Functions.2nded. 24 HOLMES.GeometricFunctionalAnalysisand 59 LANG.CyclotomicFields. ItsApplications. 60 ARNOLD.MathematicalMethodsinClassical 25 HEWITT/STROMBERG.RealandAbstract Mechanics.2nded. Analysis. 61 WHITEHEAD.ElementsofHomotopyTheory. 26 MANES.AlgebraicTheories. 62 KARGAPOLOV/MERIZJAKOV.Fundamentalsof 27 KELLEY.GeneralTopology. theTheoryofGroups. 28 ZARISKI/SAMUEL.CommutativeAlgebra. 63 BOLLOBAS.GraphTheory. Vol.I. 64 EDWARDS.FourierSeries.Vol.I.2nded. 29 ZARISKI/SAMUEL.CommutativeAlgebra. 65 WELLS.DifferentialAnalysisonComplex Vol.II. Manifolds.2nded. 30 JACOBSON.LecturesinAbstractAlgebraI. 66 WATERHOUSE.IntroductiontoAffineGroup BasicConcepts. Schemes. 31 JACOBSON.LecturesinAbstract 67 SERRE.LocalFields. AlgebraII.LinearAlgebra. 68 WEIDMANN.LinearOperatorsinHilbert 32 JACOBSON.LecturesinAbstractAlgebraIII. Spaces. TheoryofFieldsandGaloisTheory. 69 LANG.CyclotomicFieldsII. 33 HIRSCH.DifferentialTopology. 70 MASSEY.SingularHomologyTheory. 34 SPITZER.PrinciplesofRandomWalk.2nded. 71 FARKAS/KRA.RiemannSurfaces.2nded. 35 ALEXANDER/WERMER.SeveralComplex 72 STILLWELL.ClassicalTopologyand VariablesandBanachAlgebras.3rded. CombinatorialGroupTheory.2nded. 36 KELLEY/NAMIOKAetal.LinearTopological 73 HUNGERFORD.Algebra. Spaces. 74 DAVENPORT.MultiplicativeNumberTheory. 37 MONK.MathematicalLogic. 3rded. (continuedafterindex) J.A. Bondy U.S.R. Murty Graph Theory (cid:65)(cid:66)(cid:67) J.A.Bondy,PhD U.S.R.Murty,PhD Universite´Claude-BernardLyon1 MathematicsFaculty DomainedeGerland UniversityofWaterloo 50AvenueTonyGarnier 200UniversityAvenueWest 69366LyonCedex07 Waterloo,Ontario,Canada France N2L3G1 EditorialBoard S.Axler K.A.Ribet MathematicsDepartment MathematicsDepartment SanFranciscoStateUniversity UniversityofCalifornia,Berkeley SanFrancisco,CA94132 Berkeley,CA94720-3840 USA USA GraduateTextsinMathematicsseriesISSN:0072-5285 ISBN:978-1-84628-969-9 e-ISBN:978-1-84628-970-5 DOI:10.1007/978-1-84628-970-5 LibraryofCongressControlNumber:2007940370 MathematicsSubjectClassification(2000):05C;68R10 (cid:176)c J.A.Bondy&U.S.R.Murty2008 Apartfromanyfairdealingforthepurposesofresearchorprivatestudy,orcriticismorreview,aspermitted undertheCopyright,DesignsandPatentsAct1988,thispublicationmayonlybereproduced,storedortrans- mitted,inanyformorbyanymeans,withthepriorpermissioninwritingofthepublishers,orinthecaseof reprographicreproductioninaccordancewiththetermsoflicensesissuedbytheCopyrightLicensingAgency. Enquiriesconcerningreproductionoutsidethosetermsshouldbesenttothepublishers. Theuseofregisteredname,trademarks,etc.inthispublicationdoesnotimply,evenintheabsenceofaspecific statement,thatsuchnamesareexemptfromtherelevantlawsandregulationsandthereforefreeforgeneraluse. The publisher makes no representation, express or implied, with regard to the accuracy of the information containedinthisbookandcannotacceptanylegalresponsibilityorliabilityforanyerrorsoromissionsthat maybemade. Printedonacid-freepaper 9 8 7 6 5 4 3 2 1 springer.com Dedication To the memory of our dear friends and mentors Claude Berge Paul Erdo˝s Bill Tutte Preface For more than one hundred years, the development of graph theory was inspired andguidedmainlybytheFour-ColourConjecture.Theresolutionoftheconjecture byK.AppelandW.Hakenin1976,theyearinwhichourfirstbookGraph Theory with Applications appeared, marked a turning point in its history. Since then, the subject has experienced explosive growth, due in large measure to its role as an essential structure underpinning modern applied mathematics. Computer science and combinatorial optimization, in particular, draw upon and contribute to the development of the theory of graphs. Moreover, in a world where communication is of prime importance, the versatility of graphs makes them indispensable tools in the design and analysis of communication networks. Building on the foundations laid by Claude Berge, Paul Erdo˝s, Bill Tutte, and others,anewgenerationofgraph-theoristshasenrichedandtransformedthesub- ject by developing powerful new techniques, many borrowed from other areas of mathematics. These have led, in particular, to the resolution of several longstand- ing conjectures, including Berge’s Strong Perfect Graph Conjecture and Kneser’s Conjecture, both on colourings, and Gallai’s Conjecture on cycle coverings. One of the dramatic developments over the past thirty years has been the creation of the theory of graph minors by G. N. Robertson and P. D. Seymour. In alongseriesofdeeppapers,theyhaverevolutionized graphtheorybyintroducing an original and incisive way of viewing graphical structure. Developed to attack a celebrated conjecture of K. Wagner, their theory gives increased prominence to embeddings of graphs in surfaces. It has led also to polynomial-time algorithms for solving a variety of hitherto intractable problems, such as that of finding a collection of pairwise-disjoint paths between prescribed pairs of vertices. Atechniquewhichhasmetwithspectacularsuccessistheprobabilisticmethod. Introduced in the 1940s by Erdo˝s, in association with fellow Hungarians A. R´enyi andP.Tura´n,thispowerfulyetversatiletoolisbeingemployedwithever-increasing frequency and sophistication to establish the existence or nonexistence of graphs, and other combinatorial structures, with specified properties. VIII Preface As remarked above, the growth of graph theory has been due in large measure to its essential role in the applied sciences. In particular, the quest for efficient algorithmshasfuelledmuchresearchintothestructureofgraphs.Theimportance of spanning trees of various special types, such as breadth-first and depth-first trees, has become evident, and tree decompositions of graphs are a central ingre- dient in the theory of graph minors. Algorithmic graph theory borrows tools from a number of disciplines, including geometry and probability theory. The discovery by S. Cook in the early 1970s of the existence of the extensive class of seemingly intractable NP-complete problems has led to the search for efficient approxima- tion algorithms, the goal being to obtain a good approximation to the true value. Here again, probabilistic methods prove to be indispensable. Thelinksbetweengraphtheoryandotherbranchesofmathematicsarebecom- ing increasingly strong, an indication of the growing maturity of the subject. We have already noted certain connections with topology, geometry, and probability. Algebraic,analytic,andnumber-theoretictoolsarealsobeingemployedtoconsid- erable effect. Conversely, graph-theoretical methods are being applied more and more in other areas of mathematics. A notable example is Szemer´edi’s regularity lemma. Developed to solve a conjecture of Erd˝os and Tura´n, it has become an essential tool in additive number theory, as well as in extremal conbinatorics. An extensive account of this interplay can be found in the two-volume Handbook of Combinatorics. It should be evident from the above remarks that graph theory is a flour- ishing discipline. It contains a body of beautiful and powerful theorems of wide applicability. The remarkable growth of the subject is reflected in the wealth of books and monographs now available. In addition to the Handbook of Combina- torics,muchofwhichisdevotedtographtheory,andthethree-volumetreatiseon combinatorial optimization by Schrijver (2003), destined to become a classic, one can find monographs on colouring by Jensen and Toft (1995), on flows by Zhang (1997),onmatchingbyLova´szandPlummer(1986),onextremalgraphtheoryby Bolloba´s (1978), on random graphs by Bolloba´s (2001) and Janson et al. (2000), onprobabilisticmethodsbyAlonandSpencer(2000)andMolloyandReed(1998), on topological graph theory by Mohar and Thomassen (2001), on algebraic graph theory by Biggs (1993), and on digraphs by Bang-Jensen and Gutin (2001), as well as a good choice of textbooks. Another sign is the significant number of new journals dedicated to graph theory. Thepresentprojectbeganwiththeintentionofsimplymakingminorrevisions to our earlier book. However, we soon came to the realization that the changing face of the subject called for a total reorganization and enhancement of its con- tents.AswithGraph Theory with Applications,ourprimaryaimhereistopresent acoherentintroductiontothesubject,suitableasatextbookforadvancedunder- graduate and beginning graduate students in mathematics and computer science. For pedagogical reasons, we have concentrated on topics which can be covered satisfactorily in a course. The most conspicuous omission is the theory of graph minors,whichweonlytouchupon,itbeingtoocomplextobeaccordedanadequate Preface IX treatment. We have maintained as far as possible the terminology and notation of our earlier book, which are now generally accepted. Particularcarehasbeentakentoprovideasystematictreatmentofthetheory of graphs without sacrificing its intuitive and aesthetic appeal. Commonly used proof techniques are described and illustrated. Many of these are to be found in insets, whereas others, such as search trees, network flows, the regularity lemma and the local lemma, are the topics of entire sections or chapters. The exercises, of varying levels of difficulty, have been designed so as to help the reader master these techniques and to reinforce his or her grasp of the material. Those exercises which are needed for an understanding of the text are indicated by a star. The more challenging exercises are separated from the easier ones by a dividing line. A second objective of the book is to serve as an introduction to research in graph theory. To this end, sections on more advanced topics are included, and a numberofinterestingandchallengingopenproblemsarehighlightedanddiscussed in some detail. These and many more are listed in an appendix. Despitethismoreadvancedmaterial,thebookhasbeenorganizedinsuchaway thatanintroductorycourseongraphtheorymaybebasedonthefirstfewsections of selected chapters. Like number theory, graph theory is conceptually simple, yet gives rise to challenging unsolved problems. Like geometry, it is visually pleasing. Thesetwoaspects,alongwithitsdiverseapplications,makegraphtheoryanideal subject for inclusion in mathematical curricula. We have sought to convey the aesthetic appeal of graph theory by illustrating the text with many interesting graphs — a full list can be found in the index. Thecoverdesign,takenfromChapter10,depictssimultaneousembeddingsonthe projective plane of K and its dual, the Petersen graph. 6 A Web page for the book is available at http://blogs.springer.com/bondyandmurty Thereaderwillfindtherehintstoselectedexercises,backgroundtoopenproblems, other supplementary material, and an inevitable list of errata. For instructors wishing to use the book as the basis for a course, suggestions are provided as to an appropriate selection of topics, depending on the intended audience. We are indebted to many friends and colleagues for their interest in and help with this project. Tommy Jensen deserves a special word of thanks. He readthroughtheentiremanuscript,providednumerousunfailinglypertinentcom- ments, simplified and clarified several proofs, corrected many technical errors and linguistic infelicities, and made valuable suggestions. Others who went through and commented on parts of the book include Noga Alon, Roland Assous, Xavier Buchwalder, Genghua Fan, Fr´ed´eric Havet, Bill Jackson, Stephen Locke, Zsolt Tuza, and two anonymous readers. We were most fortunate to benefit in this way from their excellent knowledge and taste. Colleagues who offered advice or supplied exercises, problems, and other help- ful material include Michael Albertson, Marcelo de Carvalho, Joseph Cheriyan, Roger Entringer, Herbert Fleischner, Richard Gibbs, Luis Goddyn, Alexander X Preface Kelmans, Henry Kierstead, La´szl´o Lov´asz, Cl´audio Lucchesi, George Purdy, Di- eterRautenbach, BruceReed,BruceRichmond, NeilRobertson,Alexander Schri- jver, Paul Seymour, Miklo´s Simonovits, Balazs Szegedy, Robin Thomas, St´ephan Thomass´e,CarstenThomassen,andJacquesVerstra¨ete.Wethankthemallwarmly fortheirvariouscontributions.WearegratefulalsotoMartinCrossleyforallowing us to use (in Figure 10.24) drawings of the Mo¨bius band and the torus taken from his book Crossley (2005). Facilities and support were kindly provided by Maurice Pouzet at Universit´e Lyon 1 and Jean Fonlupt at Universit´e Paris 6. The glossary was prepared using softwaredesignedbyNicolaTalbotoftheUniversityofEastAnglia.Herpromptly- offered advice is much appreciated. Finally, we benefitted from a fruitful relation- ship with Karen Borthwick at Springer, and from the technical help provided by her colleagues Brian Bishop and Frank Ganz. We are dedicating this book to the memory of our friends Claude Berge, Paul Erdo˝s, and Bill Tutte. It owes its existence to their achievements, their guiding hands, and their personal kindness. J.A. Bondy and U.S.R. Murty September 2007