INTRODUCTION TO GRAPH THEORY

1 IiiINTRODUCTIONTO GRAPHTHEORYSECONDEDITION(2001)SOLUTIONMA NUALSUMMER2005 VERSIONc DOUGLASB. thisworkmay 's SolutionManualforIntroductiontoGraphTheo ry, byDouglasB. fewsolutionshavebeenaddedorclari edsincelastyear's (slightlyedited)annotatedsyllabusfortheo ne semestercoursetaughtfromthisbookattheUni versityof 7and93% , , , , , 7arelackingsolutionshere. Thereproblemsaretoolongordif cultforthistextoruseconceptsnotcoveredin thetext; lesareoccupiedbythestatementsof thecorrespondingproblems. Theseprob lemsretainthe. /,.!/,.C/,. /indicators. Also. /is addedtointroducethestatementsofproblemsw ithoutotherindicators. Thuseveryproblemwhosesolutionis notincludedis markedbyoneoftheindicators, foreaseof identi Thelevelofdetailinsolutionsvaries. Instructorsshouldfeelfreetowriteupsoluti onswithmoreorlessdetailaccordingtothenee dsoftheclass.

2 Timelimitations, TheauthorthanksFredGalvininparticularfor con , Meanwhile, theauthorapologizesforanyinconvenienceca usedbytheabsenceof WestiiiSolutionsPrefaceivMathematicsDepa rtment - University of IllinoisMATH 412 SYLLABUSFOR INSTRUCTORSText:West,IntroductiontoGraph THEORY ,secondedition,PrenticeHall, Hencethiscourseaimsprimarilytoimprovestu dents'writingofproofsindiscretemathemati cswhilelearningaboutthestructureof graphs. Somealgorithmsarepresentedalongtheway, andmanyoftheproofsareconstructive. TheaspectofalgorithmsemphasizedinCScours esisrunningtime;ina mathematicscourseingraphtheoryfromthisbo okthealgorithmicfocusis intendedasa , andmostof theexercisesinthetextdoso. Thematerialisinteresting, accessible, andapplicable;moststudentswhostick withthecoursewillgiveit a thecourseis theclearpresentationof solutions,which involvescarefulwriting.

3 Manyof theproblemsinthetexthavehints,eitherwher etheproblemisposedorinAppendixC (orboth).Producinga solutioninvolvestwomainsteps: ndinga cialtothelearningprocesstoprovide collabora tivestudysessions inwhich studentscandiscusshomeworkproblemsinsmal lgroupsandaninstructororteachingassistan tis , asina transition course. Somestudentsmay needfur therexplicitdiscussionsof thestructureof proofs. Such discussionappearinmanytexts, such asD'AngeloandWest,MathematicalThinking:P roblem SolvingandProofs;Eisenberg,TheMathematic alMethod:A Transitionto AdvancedMathematics;Fletcher/Patty,Found ationsof HigherMathematics;Galovich,Introductiont oMathematicalStructures;Galovich,DoingMa thematics:AnIntroductionto ProofsandProblemSolving;Solow, the rstsevenchaptersof thetext, , problemsdesignatedby.

4 /areeasierorshorterthanmost,oftengoodfor testsorfor warmup !/areparticularlyinstructive, entertaining, /makeuseof Illinoishas43 fty naltwolecturesareforoptionaltopics, * optional markingalsosuggeststostudentsthatthe (Bridg It)inSec Theplanarityalgorithm(withoutproof) appealingtostudents, alsoveryinstructiveandis coveredwhentheclassis proceedingonschedule. Otherpotentialaddi tionsincludetheapplicationsof Menger's :31, :16,21 :24,31 :1,4,7,25 :8, 14 :13 :7 :4 :20 :11,22( proof ) :10 11,16( proof ) :18 20, :9 10,13 :17vSolutionsPrefaceviCommentsTherearese veralunderlyingthemesinthecourse, andmentioningtheseatappropriatemomentshe lpsestablishcontinuity. Theseinclude1)TONCAS(TheObviousNecessary Condition(s)areAlsoSuf cient).2) )Prooftechniquessuch astheuseof extremality, theparadigmforinduc tiveproofsofconditionalstatements, andthetechniqueoftransformingaproblemint oa notsomuch becauseoftheimportanceofthePetersengraph itself, butratherbecauseit isa smallgraphandyethascomplexenoughstructur eto permitmanyinterestingexercisesto , moststudentsenterthecoursehavingbeenexpo sedtoprooftechniques, soreviewingtheseinthe rst vesec tionshasbecomelessnecessary;remarksincla sscanemphasistechniquesasreminders.

5 To minimizeconfusion, ;studentsabsorbtheadditionalmodelmoreeas ilyafterbecomingcomfortablewiththe :p3 6containmotivationalexamplesasanoverview ofthecourse;thisdiscussionshouldnotexten dpastthe rstday nomatterwhereitends(thede nitionsarelaterrepeatedwhereneeded). :Thede nitionsofpathandcycle areintendedtobeintuitive;oneshouldn'tdwe llontheheavinessof :Althoughcharacterizationof graphicsequencesis a classicaltopic,somereviewershavequestion editsimportance. Nevertheless, :Theexamplesarepresentedtomotivatethemod el;thesecanbeskippedtosavetime. ThedeBruijngraphis a ,butit takesa :Characterizationof treesis a goodplacetoaskforinputfromtheclass, :TheinductiveproofforthePr ufercorrespondenceseemstobeeasierformost studentstograspthanthefullbijectiveproof ;it alsoillus tratestheusualtypeofinductionwithtrees.

6 Moststudentsintheclasshaveseendeterminan ts, butmosthaveconsiderabledif cultyunderstand ingtheproofof theMatrixTreeTheorem;giventhetimeinvolve d,it is bestjusttostatetheresultandgiveanexample (thenexteditionwillincludea purelyinductiveproofthatusesonlydetermin antexpansion,nottheCauchy BinetFormula).Students ndthematerialongracefullabelingsenjoyabl eandilluminating;it doesn'ttakelong, butalsoit isn' :Manystudentshaveseenrootedtreesincomput erscienceand ndordinarytreesunnatural;Kruskal's algorithmshouldclarifythedis ,Dijkstra,andHuffman;herecoverKruskaland perhapsDijkstra(manystudentshaveseenthea lgorithmbutnota proofof correctness), :Skip DominatingSets ,butpresenttherestof :Students ndtheHungarianalgorithmdif cult;explicitexamplesneedtobeworkedalong withthetheoreticaldiscussionoftheequalit ysubgraph.

7 StableMatchings is verypopularwithstudentsandshouldbepresen tedunlessfarbehindinschedule. Skip FasterBipartiteMatching . :PresentallofthesubsectiononTutte's 1 factorsisintellectuallybeautifulandleads tooneproofoftheErd os Gallaiconditions, butit is notusedagaininthecourseandis an aside .SkipeverythingonEdmonds'BlossomAlgorith m:matchingalgo rithmsingeneralgraphsareimportantalgorit hmicallybutwouldrequiretoomuch timeinthiscourse;thisis recommendedreading . :Studentshavetroubledistinguishing k connected from connec tivityk and bonds from edgecuts .Bondsaredualtocyclesinthematroidalsense ;therearehintsofthisinexercisesandinChap ter7, :Students ndthissectiona bitdif ,makingit omittable, 21canbeskippedortreatedlightly,sincethem ainissueis thelocalversionof Menger's 25areappealingapplicationsthatcanbeadded ; (CSDR)is a fundamentalresultbuttakesa fairamountof :Thematerialonnetwork owisquiteeasybutcantakea longtimetopresentduetotheoverheadofde ningnewconcepts.

8 A moreappealingapplicationthatperhapsmakes thepointmoreeffectively. Skip SuppliesandDemands . :If timeis short,theproofof (Brooks'Theorem) :BesuretocoverTur an's 's The valuableasanapplicationoftheFanLemma(Men ger'sTheorem).Thesubsequentmaterialhasli mitedappealto :Theinclusion exclusionformulaforthechromaticpolynomia lisderivedhere( )withoutusinginclusion exclusion,makingit accessi bletothisclasswithoutprerequisite. However, thisproofisdif cultforstudentstofollowinfavorofthesimpl einclusion exclusionproof, whichwillbeoptionalsincethatformulais notprerequisiteforthecourse. Hencethisformulashouldbeomittedunlessstu dentsknowinclusion ,butthesecanalsobetreatedlightlyif shortof time. Skip CountingAcyclicOrientations . :Thetechnicalde nitionsof objectsintheplaneshouldbetreatedveryligh tly.

9 Itisbettertobeinformalhere, withoutwritingoutformalde nitionsunlessexplicitlyrequestedbystuden ts. Outerplanargraphsareusefulasa much easierclassonwhich tosolveproblems(exercises!)likethoseonpl anargraphs; 20arefundamentalobservationsaboutouterpl anargraphs, butotheritemsaremoreimportantif (polyhedra)is 7onKuratowski's Theoremcanbepresentedlightly, leavingtheannoyingdetailsasreading;thesu bsequentmaterialonconvexembeddingof3 connectedgraphsis much moreinter esting. Presentationoftheplanarityalgorithmis appealingbutoptional;skiptheproofthatit :Thefourcolorproblemis popular;forundergraduates, showthe awinKempe's proof (p271),butdon'tpresentthedischargin gruleun lessaheadofschedule. Students ndtheconceptofcrossingnumbereasytograsp, buttheresultsarefairlydif cult;trytogoasfarastherecur timeforunder graduates.

10 Interestedstudentscanbeadvisedtoreadther estof :TheproofofVizing's Theoremisoneofthemoredif cultinthecourse, butundergraduatescangainfollowit whenit ispresentedwithsuf shortoftime. Skip CharacterizationofLineGraphs ,althoughif timeandinterestis plenti fulthenecessityof Krausz's :Chv atal's theorem( )is notashardtopresentasit ,theproofis somewhattechnicalandcanbeskipped( ).Moreappealingis theChv atal Erd osTheorem( ), CyclesinDirectedGraphs . :ThetheoremsofTaitandGrinbergmakea niceculminationtotherequiredmaterialofth ecourse. Skip Snarks and FlowsandCycleCovers .Nevertheless, timepermits, materialfromthe rstpartofsectionsofChapter8 canbepresentedtogivethestudentsa (RamseyTheoryorSperner's Lemma) (RandomGraphs).AlsopossiblearetheGossipP roblem(orotheritems)fromSec The (PerfectGraphs)may quiremoreinvestmentinpreliminarymaterial andthusarelesssuitableforgivinga glimpse.