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