g(G)foreachi=1,2,···,k.Itfollowsthat
v+k 1vv=v(G)≥k(g 1)+1= g(G)=g≤=.kk
Ex4.3.13Assumeκ(G)=k≥1andd(G)≥3.Letx,y∈V(G)suchthatdG(x,y)=d(G).ByMenger’stheorem,ζG(x,y)≥κ(G)=k≥1andζG(y,x)≥κ(G)=k≥1.LetP1,P2,···,Pkbekinternallydisjoint(x,y)-pathsinG.Then
+d+(x) k≥δ(G) k,G d (y) k≥δ(G) k.G
+ Sinced(G)≥3,NG(x)∩NG(y)= .Itfollowsthat
v≥k
i=1(v(Pi) 1)+2+δ+(G) k+δ (G) k≥k(d 1)+2+δ++δ 2k=k(d 3)+δ++δ +2.
8