HintstoExercisesinChapter1
Ex1.2.6Byε(G)=ε(Gc)andε(G)+ε(Gc)=ε(Kv).
Ex1.3.5ByTheorem1andd+D(x)+dG(x)=v 1foranyx∈V(D).
Ex1.3.6(a)Bytheequalities(1,3).
(b)Byd+D(x)+dG(x)=v 1foranyx∈V(D).
Ex1.4.2AgeneralizationofExample1.4.2.
Ex1.4.4Byde nitionofthelinegraph.
Ex1.4.5Byde nitionoftheCartesianproduct.
Ex1.5.4(c)ByExample1.4.1
Ex1.5.6(a)Therearetwowaystoproveit.TheonewayistoconsiderthenumberviofthecomponentGiandobtain
(G)=ω
i=11 1 211 (Gi)≤vi(vi 1)=vi v≤(v ω)(v ω+1).2i=12i=122ωω
AnotherwayistoconsiderGasagraphwithedgesaslargeaspossible,andtoprovethatallcomponentsofGistrivialexceptone.
(b)Bycontradiction.
Ex1.5.7Theproofof(a)issimilartoEx1.5.6(a).Toprove(b),de neafunction
1f(ω)=(v ω)(v ω+1)+(ω 1)(2v ω).2
Itisconvexontheinterval[2,v]forv≥3.
Ex1.6.3Therearesomewrongsinthisexercise.Shouldaddthatthecondition“ifGisstronglyconnectedthen”to(b)anddelete“andTheorem1.4”from(c).Theproofof(b).Thefacesthatv(G)=v(L(G))=ε(G)=ε(L(G))and
+ ε=dG(x)dG(x)≥1=ν=ε,
x∈V(G)
impliesd+G(x)=dG(x)=1foranyx∈V(G).x∈V(G)
Ex1.6.4SimilartoExample1.6.4.
Ex1.6.6Thereis awinthisexercise.Shouldaddthatthecondition“ifGisanundirectedgraph”to(a).
Ex1.7.4Firstprovethatv(T)≥2k+1.Withoutlossofgenerality,assumek=δ+.ByTheorem1.1, +k·v≤dT(x)=d T(x).
x∈V(T)x∈V(T)
1