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

Alsosince|Ei|≤vforeachi=1,2,···, ,bythecondition(b),wehavecandeduceacontradictionasfollows.

v

2<ε=

i=1|Ei|≤ v 2.

v

2(c)SinceGhasoddorderandisregular,wehaveε= > 2.By(b),G

belongstoclasstwo.

(d)IfGisoddorder,theassertionholdsby(b).WenowassumeGisevenorder.Letxbeacut-vertexofG.ThentherearetwosubgraphsHandKsuchthatG=H∪KandV(H)∩V(K)={x}.Withoutlossofgenerality,supposethatHhasoddorderh.Then1≤dH(x)≤ (G),andso

1h1.ε(H)=((h 1) +dH(x))>(h 1) = 222

By(b),Hbelongstoclasstwo,andsodoesG. Ex6.2.5Bycontradiction.Supposethatχ(G)=k>2 .Byremovingsu -cientlymanyedgesfromG(ifnecessary),wemayassumethatχ (G e)=k 1,foreachedgeeofG.ItfollowsfromTheorem6.3thatk≤ (G)+µ(G),andsotheremustexistverticesxandywhicharejoinedbyatleastk edges.

WenowcoloralloftheedgesofGexceptoneoftheedgesjoiningxandy;sinceχ (G e)=k 1,thiscoloringcanbedonewithk 1colors.Nowthenumberofcolorsmissingfromxory(orboth)cannotexceed(k 1) (µ 1),whichinturncannotexceed ,sincek≤ +µ.Butthenumberofcolorsmissingfromxisatleast(k 1) ( 1)=k ,andsimilarlythenumberofcolorsmissingfromyisatleastk .Itfollowsthatthenumberof missingfrombothxandyisatleast 3colors(2k ) ,whichispositivesincek> .Byassigningoneofthesemissingcolorstotheun-colorededgejoiningxandy,wehavecoloredalloftheedgesofGusingonlyk 1colors.therebycontradictingthefactthatχ (G)=k. v 3

Ex6.2.6LetLbethelineofasimplegraphG.ByExercise6.2.3,χ (G)=χ(L).Since (G)≥3,Lisnetheranoddcyclenoracompletegraph,and (L)≤2 (G) 2.Thus,ByBrooks’theorem,χ (G)=χ(L)≤ (L)≤2 (G) 2.

13

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