图论及其应用徐俊明课后习题提示(7)

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库图论及其应用徐俊明课后习题提示(7)在线全文阅读。