HintstoExercisesinChapter4
Ex4.1.2(b)Foranytwodistinctverticesu,v∈S,ifa=(u,v)∈E(G),thenf+(u)containsf(a)andf (v)containsf(a),thatis,f(a)doesnotcontributetothesum.Inotherwords,anyedgeasuchthatf(a)contributestothesumhasexactlyoneend-vertexinS.
Ex4.1.4SeetheproofofTheorem4.1.
Ex4.2.3(a)Notethatthecondition“d+G(x) dG(y)=k”shouldbereplacedby
“d+G(x) dG(x)=k”.
OneofthewaysistouseExercise1.8.3.directly.TheotherwayisuseMenger’stheorem4.2.Infact,let(S,)beaλ-cutofG.ThenηG(x,y)=λG(x,y)=|(S,≥ + |(S,)| |(S)|=(d+G(u) dG(u))=dG(x) dG(x)=k.
u∈S
Ex4.2.4Theassertioncanbeprovedstructurally.Letk=dG(x)≤dG(y),A=NG(x)∩NG(y)={u1,u2,···,uh},X=NG(x) A {y}={x1,x2,···,xa},X=NG(y) A {x}={y1,y2,···,yb}.Thena≤bandk=h+a+δxy,whereδxyisequaltooneifxandyadjacent,equaltozerootherwise.
Foreachui∈A,Pi=(x,ui,y)isanxy-pathoflengthtwo.Pδxy=xyifxyexists.
Sinced(G)≤2,thereareaedgedisjointxjyj-pathsQj(j=1,2,···,a)oflengthatmosttwo.LetPh+j=xxj+Qj+yjyforj=1,2,···,a.Thus,P1,P2,···,Ph+a+δxyarekedgedisjointxy-pathsoflengthatmost4.
Ex4.2.5Notethatthecondition“k≥2”shouldbeaddedtotheexercise.LetxandybetwoverticesinGsuchthatdG(x,y)=d(G).SinceGisk-regularand
k≥2,thereexistsz∈NG(y)di erentfromx.Considerk(x,z)-pathsP1,P2,···,Pk,
oneofthem,sayPi,mustusethevertexy,whoselengthε(Pi)≥dG(x,y)+1=d(G)+1.Ex4.3.3ReduceittoExample4.3.2.
Ex4.3.10ApplyMenger’stheorem(4.3)tothegraphHobtainedfrombyaddinganewvertexyandkedgesfromxitoyforeachi=1,2,···,k.
Ex4.3.11Withoutlossofgenerality,assumek≥3.LetSbeasetofkverticesandCbeacyclethatcontainverticesinSaslargeaspossible.Letm=|V(C)∩S|.Thenm≥2.Wanttoprovem=kbycontradiction.LetxbeavertexinSnotin
http://www.77cn.com.cnbeltheverticesinS∩V(C)ass1,s2,···,sminsomegivendirectionofC.ByExercise4.3.10,thereareminternallydisjoint(x,si)-pathsPi(i=1,2,···,m)inG.Ifm<k,thens1,s2,···,smpartitionsCintomsections,ofwhichatleastonecontainsnovertexinSexceptend-vertices.Assume(s1,s2)-sectionC containsnovertexinS.Then,C ∪P1∪P2formsacycleinG,whichcontainsverticesinSismorethanCdoessincex∈/V(C),acontradiction.
Ex4.3.12Letx∈V(G)andletB={y1,y2,···,yk} NG(x).Byexercise4.3.10,
therearekinternallydisjoint(x,yi)-pathsPi(i=1,2,···,k)inG.Thus,v(Pi)≥g=
7