图论导论(完全)
introductorytextshouldbeleanandconcentrateontheessentialsoas toofferguidancetothosenewtothefield.Asagraduatetext.moreover itshouldgettotheheartofthematterquickly:afterall.theideaisto conveyatleastanimpressionofthedepthandmethodsofthesubject Ontheotherhand,ithasbeenmyparticularconcerntowritewith ufficientdetailtomakethetextenjoyableandeasytoread:guiding questionsandideaswillbediscussedexplicitly,andallproofspresented willberigorousandconplete Atypicalchapter,therefore,beginswithabriefdiscussionofwhat arctheguidingqucstionsinthcarcaitcovers,continueswithasuccinct accountofitsclassicresults(oftelwithsimplifiedproofs),anldthen presentsoneortwodeepert.heoremsthatbringoutthefullflavourof thatarea.Theproofsoftheselatterresultsaretypicallyprecededby(or interspersedwith)aninformalaccountoftheirmainideas,butarethen presentedformallyatthesamelevelofdetailastheirsimplercounter parts.Isoonnoticedthat,asaconsequence,someofthoseproofscame outratherlongerinprintthanseemedfairtotheiroftenbeautifull simpleconception.Iwouldhope,however,thatevenfortheprofessional readertherelativelydetailedaccountofthoseproofswillatleasthell tominimizereadingtime. Ifdesired.thistextcanbeusedforalecturecoursewithlittleor nofurtherpreparation.Thesimplestwaytodothiswouldbetofollow theorderofpresentation,chapterbychapter:apartfromtwoclearly markedexceptions,anyresultsusedintheproofofothersprecedethe inthetext Alternatively,alecturermaywishtodividethematerialintoaneasy basiccourseforonesemester,andamorechallengingfollow-upcourse oranother.Tohelpwiththepreparationofcoursesdeviatingfromthe orderofpresentation,Ihavelistedinthemarginnexttoeachproofthe referencenumbersofthoseresultsthatareusedinthatproof.These referencesaregiveninroundbrackets:forexample,areference(4.1.2) inthemarginnexttotheproofofTheorem4.3.2indicatesthatLemma 4.1.2willbcuscdinthisproof.Correspondingly,inthemarginncxtto Lemma4.1.2thereisareference[4.3.2(insquarebrackets)informing thereaderthatthislemmawillbeusedintheproofofTheorem4.3.2 Notethatthissystemappliesbetweendifferentsectionsonly(ofthesame orofdifferentchaptersthesectionsthemselvesarewrittenasunitsand best,readintheirorderofpresentation Themathematicalprerequisitesforthisbook,asformostgraph theorytexts,areminimal:afirstgroundinginlinearalgebraisassumed forChapter1.9andonceinChapter5.5,somebasictopologicalcon ceptsabouttheEuclideanplaneand3-spaceareusedinChapter4,and apreviousfirstencounterwithelementaryprobabilitywillhelpwith Chapter11.(Evenhere,allthatisassumedformallyistheknowledge ofbasicdefinitions:thefewprobabilistictoolsusedaredevelopedinthe Preface text.)TherearetwoareasofgraphtheorywhichIfindbothfascinat ingandimportant,especiallyfromtheperspectiveofpuremathematics adoptedhere,butwhicharenotcoveredinthisbook:thesearealgebraic graphtheoryandinfinitegraphs Attheendofeachchapter,thereisasectionwithexercisesand anotherwithbibliographicalandhistoricalnotes.Manyoftheexercises werechosentocomplementthemainnarrativeofthetext:theyillus- tratenlewconcepts,showhowanlewinvariantrelatestoearlierones orindicatewaysinwhicharesultstatedinthetextisbestpossible Particularlyeasyexercisesareidentifiedbythesuperscript,themore challengingonescarrya+.Thenotesareintendedtoguidethereader ontofurtherreading,inparticulartoanymonographsorsurveyarticles onthethemeofthatchapter.Theyalsooffersomehistoricalandother remarksonthematerialpresentedinthetext Endsofproofsaremarkedbythesymbolu.Wherethissymbolis founddirectlybelowaformalassertion,itmeansthattheproofshould bcclcaraftcrwhathasbccnsaid--aclaimwaitingtobeverified!Thcrc arealsosomedeepertheoremswhicharestated,withoutproof,asback- groundinformation:thesecanbeidentifiedbytheabsenceofbothproof and口 Almosteverybookcontainserrors,andthisonewillhardlybean exception.IshalltrytopostontheWebanycorrectionsthatbecome necessary.Therelevantsitemaychangeintime,butwillalwaysbe accessibleviathefollowingtwoaddresses http://www.springer-ny.com/supplements/diestel/ http://www.springer.de/catalog/html-files/deutsch/math/3540609180.html Pleaseletmeknowaboutanyerrorsyoufind Littleinatextbookistrulyoriginal:eventhestyleofwritingand ofpresentationwillinva.riablybeinfluencedbyexamples.Thebookthat nodoubtinfluencedmemostistheclassicGTMgraphtheorytextby Bollobas:itwasinthecourserecordedbythistextthatIlearntmyfirst graphtheoryasastudent.Anyonewhoknowsthisbookwellwillfeel itsinfluencehere,despitealldifferencesincontentsandpresentation Ishouldliketothankallwhogavesogenerouslyofthcirtimc knowledgeandadviceillCOllllectiolwiththisbook.Ihavebenefited particularlyfromthehelpofn.Alon,G.Brightwell,R.Gillett,R.Halin M.Hintz.AHuck.ILeader.TLuczak.W.Mader.vRodl.A.D.Scott P.D.Seymour,G.Simonyi,M.Skoviera,R.Thomas,C.Thomassenand P.Valtr.IamparticularlygratefulalsotoTommyR.Jensen,whotaught memuchaboutcolouringandallIknowaboutk-flows,andwhoinvested immenseamountsofdiligenceandenergyinhisproofreadingofthepre liminarygermanversionofthisbook March1997 RD relace aboutthesecondedition Naturally.Iamdelightedathavingtowritethisaddendumsosoonafter thisbookcamcoutinthesummerof1997.Itisparticularlygratifying tohearthatpeoplearegraduallyadoptingitnotonlyfortheirpersonal lIsehutmoreandmorealsoasacoursetext;this,afterall,wasmyaim whenIwroteit,andmyexcuseforagonizingmoreoverpresentation thanImightotherwisehavedone. Therearetwomajorchanges.Thelastchapterongraphminors nowgivesacompleteproofofoneofthemajorresultsoftheRobertson Seymourtheory,theirtheoremthatexcludingagraphasaminorbounds thetree-widthifandonlyifthatgraphisplanar.Thisshortproofdid notexistwhenIwrotethefirstedition,whichiswhyithenincludeda shortproofofthenextbestthingtheanalogousresultforpath-width ThattheoremhasnowbeendroppedfromChapter12.Anotheraddition inthischapteristhatthetree-widthdualitytheorem,Theorem12.3.9 nowcomeswitha(short)prooftoo Thesecondmajorchangeistheadditionofacompletesetofhints fortheexercises.ThesearelargelyTollllllyJensenr'swork,alldIalll gratefulforthetimehedonatedtothisproject.Theaimofthesehints istohclpthoscwhouscthebooktostudygraphthcoryonthcirown butnottospoilthefun.Theexercises,includinghints,continuetobe intendedforclassroomuse apartfromthesetwochanges.thereareafewadditions.Themost noticableofthesearetheformalintroductionofdepth-firstsearchtrees inSection1.5(whichhasledtosomesimplificationsinlaterproofs)and aningeniousnewproofofMenger'stheoremduetoBohme,Goringand Harant(whichhasnototherwisebeenpublished Finally,thereisdhostofSInallsimplificationsalldclarificatiOns ofargumentsthatInoticedasItaughtfromthebook,orwhich were pointedouttomebyothers.ToalltheseIoffermyspecialthanks TheWebsiteforthebookhasfollowedmeto http://www.math.uni-hamburg.de/home/diestel/books/graph.theory Iexpectthisaddresstobestableforsometime Oncemore,mythanksgotoallwhocontributedtothissecond editionbycommentingonthefirst-andilookforwardtofurthercom Inlets December1999 RD Preface aboutthethirdedition Thereisnodenyingthatthisbookhasgrown.Isitstillas'leanand concentratingontheessentialasIsaiditshouldbewhenIwrotethe prefacetothefirstedition,nowalmosteightyearsago? Ibelievethatitis,perhapsIlowInorethallever.Sowhythieincrease involume?PartoftheansweristhatIhavecontinuedtopursuethe originaldualaimofofferingtwodifferentthingsbetweenonepairof covers. arcliablcfirstintroductiontographthcorythatcanbcuscdcithcr forpersonalstudyorasacoursetext agraduatetextthatofferssomedepthinselectedareas Foreachoftheseaims.somematerialhasbeenadded.Someofthis coversnewtopics,whichcanbeincludedorskippedasdesiredAn exampleattheintroductorylevelisthenewsectiononpackingand coveringwiththeErdos-Posatheorem,ortheinclusionofth nestable marriagetheoreminthematchingchapter.Anexampleatthegraduate levelistherobertson-Seymourstructuretheoremforgraphswithouta givenminor:aresultthattakesafewlinestostate,butonewhichisin creasinglyreliedonintheliterature,sothlatilleasilyaccessiblereference seemsdesirable.Anotheraddition,alsointhechapterongraphminors isanewproofofthe'Kuratowskitheoremforhighersurfaces'aproof whichillustratestheinterplaybetweengraphminortheoryandsurface topologybetterthanwaspreviouslypossible.Theproofiscomplemented Dyanappendixonsurfaces,whichsuppliestherequiredbackgroundand alsoshedssomemorelightontheproofofthegraphminortheorem Changesthataffectpreviouslyexistingmaterialarerare,exceptfor countlesslocalimprovementsintendedtoconsolidateandpolishrather thanchangc.Iamawarethat,asthisbookisincreasinglyadoptedas acoursetext.thereisacertaindesireforstability.Manyoftheselocal improvementsaretheresultofgenerousfeedbackIgotfromcolleagues usingthebookinthisway,andIamverygratefulfortheirhelpand Therearealsosomelocaladditions.Mostofthesedevelopedfrom myownnotes,pencilledinthemarginasipreparedtoteachfromt book.Theytypicallycomplementanimportantbuttechnicalproof whenifeltthatitsessentialideasInightgetoverlookedintheformal write-up.Forexample,theproofoftheErdos-Stonetheoremnowhas aninformalpost-mortemthatlooksathowexactlytheregularitylemma comestobeappliedinit.Unliketheformalproof,thediscussionstarts outfromthemainidea,andfinallyarrivesathowtheparameterstobe declaredatthestartoftheformalproofmustbespecified.Similarly thereisnowadiscussionpointingtosomeideasintheproofoftheperfect graphtheorem.However,inallthesecasestheformalproofshavebeen leftessentiallyuntouched relace Theonlysubstantialchangetoexistingmaterialisthattheold Theorem8.1.1(thatcr-nedgesforceaTK)seemstohavelostits nice(andlong)proof.Previously,thisproofhadservedasawelcome opportunitytoexplainsomemethodsinsparseextremalgraphtheory. Thesemethodshavemigratedtotheconnectivitychapter,wherethey nowliveundertheroofofthenewproofbyThomasandWollanthat8kn edgesmakca2k-conncctcdgraphke-linkcdSothcyarcstillthcrc,Icancr thalleverbefore,alldjustpresentingthemselvesunderallewguise.A aconsequenceofthischange,thetwoearlierchaptersondenseand sparseextremalgraphtheorycouldbereunited,toformanewchapter appropriatelynamedasLrctremalGraphTheory Finally,thereisanentirelynewchapter,oninfinitegraphs.When graphtheoryfirstemergedasamathematicaldiscipline,finiteandinfi- nitegraphswereusuallytreatedonapar.Thishaschangedinrecent years,whichIseeasaregrettableloss:infinitegraphiscontinuetopro videanaturalandfrequentlyusedbridgetootherfieldsofmathematics andthcyholdsomcspccialfascinationofthcirown.Oncaspectofthis isthatproofsoftenhavetobemoreconstructiveandalgorithmicin naturethantheirfinitecounterparts.Theinfiniteversionofmenger's theoreminSection8.4isatypicalexample:itoffersalgorithmicinsights intoconnectivityproblemsinnetworksthatareinvisibletotheslick inductiveproofsofthefinitetheoremgiveninChapter3.3 Oncemore,mythanksgotoallthereadersandcolleagueswhose commcntshelpedtoimprovcthebook.IamparticularlygratefultoImrc Leaderforhisjudiciouscommentsonthewholeoftheinfinitechapter;to mygraphtheoryseminar,inparticulartoLilianMatthiesenandPhilipp Spriissel,forgivingthechapteratestrunandsolvingallitsexercises (ofwhicheightysurvivedtheirscrutiny)toAngelosGeorgakopoulosfor muchproofreadingelsewhere;toMelanieWinMyintforrecompilingthe indexandextendingitsubstantially;andtoTimStelldingerfornursing thewhaleonpage366untilitwasstrongenoughtocarryitsbaby dinosaur May2005 RD Contents Preface 1.TheB 1.1Graphs 1.2Thedegreeofavertex 1.3Pathsandcycles 1.4Connectivity*x 1.5Treesandforests* 13 1.6Bipartite 1.7Contractionandmino/s* ·· 1.8Eulertours*k 1.9Sonelinearalgebra 1.10Othernotionsofgraphs Exercises 30 「o 32 2.Matching,CoveringandPacking chinginbipartitegrap 2.2Matchingingeneralgraphs*) ····· 39 2.3Packingandcovering 44 2.4Tree-packingandarboricity 46 2.5Pathcovers 49 Exercises N 53 Sectionsmarkedbyanasteriskarerecommendedforafirstcourse first Xlv Contents 3.Connectivity 3.12-Connectedgraphsandsubgraphs* 3.2Thestructureof3-connectedgraphs/* 55 57 3.3Menger'stheorem 3.4Mader'stheorem 3.5Linkingpairsofvertices 69 Exercises Notes 4.Planargraphs 4.1Topologicalprerequisites 4.2Planegraphs 4.3Drawings 1.Planargraphs:Kuratowski,'stheorem* 4.5Algebraicplanaritycriteria ..,101 4.6Planedualit 103 E 106 Notes 109 ouring 111 5.1Colouringmapsandplanargraphs 112 5.2Colouringvert ..,114 5.3Colouringedges 119 5.4Listcolouring.............. 121 grap 126 Exercises 133 Note 136 6.Flows 139 6.1Circulations(*) ··.·· ......140 6.2Flowsinnetworks 141 6.3Group-valuedFlows....... 144 6.4k-Flowsforsmallk 149 6.5Flow-colouringduality 152 6.6Tutte'sHowconjecturEs......... 156 160 oles Contents 7.ExtremalGraphTheory 7.1Subgraphs 164 7.2Minors() 169 7.3Hadwigersconjecture* 172 7.1Szemeredi'sregularitylemma 7.5Applyingtheregularitylemma 183 Exercises 189 Notes 192 8.Infinitegraphs 195 8.1Basicnotions,factsandtechniques 196 8.2Paths,trees,andends(k) 204 8.3Homogeneousanduniversalgraphs 212 8.4Connectivityalldinatching 8.5Thetopologicalendspace 226 xercises 237 244 9.RamseyTheoryforGraphs 251 9.1Ramsey'soriginaltheorems 252 9.2Ramseynumbers() 255 9.3InducedRamseytheorems 9.4Ramseypropertiesandconnectivity 26 Exercises 10.HamiltonCycles 275 10.1Simplesufficientconditi 10.2Hamiltoncyclesanddegreesequences 278 10.3Hamiltoncyclesinthesquareofagraph 281 289 Notes 290