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