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

HintstoExercisesinChapter3

Ex3.1.4Usingthefollowingthreeequalities:

3v ε=6,

v=v3+v4+v5+v6+v7+v8+···+v ,

2ε=3v3+4v4+5v5+6v6+7v7+8v8+···+ v .

Ex3.1.6Usingthefollowingthreeequalities:

3v=φ1+2φ2+3φ3+4φ4+5φ5+6φ6+7φ7+8φ8+···,

2ε=φ1+2φ2+3φ3+4φ4+5φ5+6φ6+7φ7+8φ8+···,

φ=φ1+φ2+φ3+φ4+φ5+φ6+φ7+φ8+···,

andEuler’sformulav ε+φ=2.

Ex3.1.7Withoutlossofgenerality,assumethatGisaplanegraph.ByTheorem

3.2andEuler’sformula, 2ε(G)=dG(f)≥gφ=g(2 v+ε)= g(v 2)+gε.

f∈F(G)

1v(v 1),wehaveEx3.1.8Fromε≤3v 6andε(G)+ε(Gc)=11ε(Gc)≥v(v 1) 3(v 3)=(v2 7v+12)>3v 6forv≥11.22

Ex3.1.14Withoutlossofgenerality,supposethatGismaximalandthat{d1,d2,···,dv}isthedegree-sequenceofG.Then

v

i=1di=2ε=6n 12.

v

i=1Letf(d1,d2,···,dv)=

(a)For3≤di≤v 1andv≥4,d2i.

f(d1,d2,···,dv)≤f(3,3,4,4,···,4,v 1,v 1)

=18+16(v 4)+2(v 1)2=2(v+3)2 62.

(b)Notethatδ≥4impliesv>5.For4≤di≤v 1andv>5,

f(d1,d2,···,dv)≤f(4,4,···,4,v 2,v 2)=16(v 2)+2(v 2)2

=2(v+3)2 4v 42<2(v+3)2 62.

Ex3.2.3LetV(G)={x,y,z,x4,x5,···,xv}.ByKuratowski’stheorem,GcontainsnoK3,3.Thereexistsatmosttwoxi,whichallareadjacenttox,y,z.Thenumberofedgesbetween{x,y,z}andV\{x,y,z}isatmost2·3+(n 5)·2=2n 4.ItfollowsthatdG(x)+dG(y)+dG(z)≤6+(2n 4)=2n+2.

6

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