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

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

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