搜索
AppendixBHintstoSelectedExercisesSection1.11.1.2(b)ObservethatasimplebipartitegraphwiththemaximumnumberofedgesisnecessarilycompletebipartiteandthatKr,shasrsedges.Nowshowthatifs−r≥2,thenKr+1,s−1hasmoreedgesthanKr,s.Alternatively,showthatn2/4−r(n−r)isaperfectsquare,andthusnonnegative.1.1.7(b)Todeterminee(Qn)applyTheorem1.1.1.1.9(a)Countingintwoways(seeinset).1.1.10FindupperboundsonthedegreesandapplyTheorem1.1.1.1.11ThisisageneralizationofExercise1.1.2.Useasimilarprooftechnique.1.1.12IfGisnotconnected,thereisapartition(X,Y)ofVsuchthatnoedgeofGjoinsavertexinXtoavertexinY.WhatisthelargestnumberofedgesthatGcanhaveif|X|=rand|Y|=n−r?1.1.13ObservethatifagraphGisdisconnected,thenthereexistsasubsetXofV,with|X|≤⌊n/2⌋,suchthatnoedgeofGjoinsavertexinXtoavertexinV\X.1.1.15ObservethatasetofvectorsoverGF(2)islinearlydependentifandonlyifitcontainsasubsetwhosesumisthezerovector.1.1.16(a)Necessity:applyTheorem1.1.Sufficiency:howmanydi’sareodd?(b)Necessity:applyTheorem1.1.Sufficiency:inductionon(Pni=2di)−d1.1.1.18(b)Countingintwoways.LetG=(V,E),whereV={v1,v2,...,vn}andd(vi)=di,1≤i≤n.SetX:={v1,v2,...,vk}.Forvi∈X,findalowerboundonthenumberofedgesjoiningvitoverticesinV\X.Forvi∈V\X,findanupperboundonthenumberofedgesjoiningvitoverticesinX.DeducelowerandupperboundsonthenumberofedgeswithoneendinXandtheotherinV\X.1.1.19(a)Toprovethenecessity,firstshowthatifGisasimplegraphwithu1v1,u2v2∈Eandu1v2,u2v16∈E,then(G\{u1v1,u2v2})+{u1v2,u2v1}hasthesamedegreesequenceasG.Deducethatifdisgraphic,thenthereisasimplegraphGwithvertexset{v1,v2,...,vn}suchthatd(vi)=di,1≤i≤n,andN(v1)={v2,v3,...,vd1+1}.1.1.20DefineagraphonSinwhichxiandxjareadjacentifandonlyiftheyareatdistanceone.Howlargecanthedegreeofavertexbeinthisgraph?1.1.21(a)Thisisaclassicalresultoflinearalgebra,andistrueforanyrealsymmetricmatrix.(b)ThisistrueforanyintegersquarematrixA.Supposethatλ:=p/qisaneigenvalueofA,wherepandqarecoprimeintegers.Assumethatq1.Usingthefactthatascalarmultipleofaneigenvectorisalsoaneigenvector,showthatthereexistsanintegraleigenvectorcorrespondingtoλnotallofwhosecoefficientsaredivisiblebyq.Deriveacontradiction.1.1.24(a)ConsiderthecasewhereG=(V,E)issimple.LetV={v1,v2,...,vn}.AneigenvectorofGcorrespondingtoaneigenvalueλmaybeviewedasaweightfunctiononVsuchthatthesumoftheweightsontheneighboursofavertexisequaltoλtimestheweightofthevertex.Chooseaneigenvectorx=(x1,x2,...,xn)ofλsuchthat|xj|:=max{|xi|:1≤i≤n}=1,andconsiderthevertexvj.Section1.21.2.14(a)UseExercise1.2.11toreducethenumberofcasestoconsider.1.2.16(c)Howmanyedgeshasaself-complementarygraph?(d)AnisomorphismmappingGtoGinducesapairingoftheverticesofG.Whatcanyousayabouttheirdegrees?1.2.17SinceGisnotvertex-transitive,thereexistverticesxandysuchthatnoautomorphismofGmapsxtoy.LetXandYdenotetheorbitsofxandy,respectively.Consideraneighbourzofx.UsingthefactthatGisedge-transitiveandthatyisnotisolated,showthatz∈Y\X.Nowshowthat(X,Y)isabipartitionofG.1.2.18(b)ToshowthattheFolkmangraphisnotvertex-transitive,observethatitisbipartite.Findapropertyoftheverticesinonepartthatisnotsharedbytheverticesintheotherpart.1.2.20ByExercise1.2.8,anautomorphismofGcanberegardedasapermutationmatrixPsuchthatPAPt=A.UsingthefactthatPt=P−1(why?),showthatifxisaneigenvectorofGcorrespondingtoaneigenvalueλ,thensoisPx.NowusethefactthatGhasndistincteigenvalues,thateigenvectorscorrespondingtodistincteigenvaluesareorthogonal(why?),andthatPisapermutationmatrix,todeducethatPx=±x.Conclude.Section1.31.3.7(b)ForeachofthefourtrianglesinthegraphofFigure1.20,apply(a)tothesetofthreeintervalsrepresentedbyitsvertices.Deducethatoneofthesixintervalsmustmeetallfiveoftheotherintervals.1.3.15(a)Assumingthat|X|≥|Y|,showthat1|X|(|Y|−d(x))≥1|Y|(|X|−d(y))forallxy/∈E.Nowapplytheprooftechniqueofcountingintwowaystodeducethat|X|=|Y|.1.3.17(a)(i)ThecomplementofL(K4)isa1-regulargraphonsixvertices.UsethisfacttoshowthatAut(L(K4))andAut(K4)havedifferentorders.(ii)Supposethatn≥3,n6=4.ShowthatanautomorphismofKninducesanautomorphismofL(Kn).DeducethatthesymmetricgroupSnisasubgroupofAut(L(Kn)).NotingthatanautomorphismofL(Kn)mapsadjacentedgesofKntoadjacentedges,showthateveryautomorphismofL(Kn)isinducedbyanautomorphismofKn.1.3.18(c)Uptoisomorphism,therearejusttwogroupsoforderten,namelyZ10andZ2×Z5.Proceedbyconsideringvariouscases(seeHolton,D.A.andSheehan,J.(1993).ThePetersenGraph.CambridgeUniversityPress,pp.292–293).Section1.51.5.7(a)LetBbeanr×rsubmatrixofM.Ifr=1,detB=0,±1.Supposethatr≥2.IfBhasacolumnof0s,orifeachcolumnofBhastwononzeroentries,thendetB=0(why?).Ifnot,proceedbyinduction.1.5.8Thisexerciseissomewhatchallengingatthisearlystageofthebook.ItwouldbemoreappropriateforSection3.4.1.5.12(b)LetxybeafixededgeofG.First,showthatthereisnoautomorphismofGwhichmapstheorderedpair(x,y)toitsconverse(y,x).Thenshowthat,foreveryedgeuvofG,theorbitoftheorderedpair(x,y)undertheautomorphismgroupofGincludesexactlyoneofthetwoorderedpairs(u,v)and(v,u)butnotboth.Nowobtainadirectedgraph→Gbyorientinganedgeuvfromutovif(u,v)isintheorbitof(x,y)andfromvtou,otherwise.ShowthateveryautomorphismofGisalsoanautomorphismof→G.Concludethat→Gisvert