Thus,
2kv≤
x∈V(T)[d+T(x)+d T(x)]= x∈V(T)(v 1)=v(v 1),
whichmeansthatv(T)≥2k+1andtheequalityholdsifandonlyifTisk-regular.WenowshowthatTcontainsadirectedcycleoflength≥2k+1byinductiononv≥2k+1.Ifv=2k+1,thenTisk-regularand,hence,Tisbalanced.Bytheexercise
1.5.4(c),Tisstronglyconnected.ByTheorem1.5,Tcontainsadirectedcycleoflength2k+1.
Nowassumethattheconclusionistrueifv=j≥2k+1andletv=j+1.IfTisstronglyconnected,thenTcontainsadirectedcycleoflengthatleast2k+1byTheorem1.5.NowassumethatTisnotstronglyconnectedandletHbeastronglyconnectedcomponentofTwithvertex-setSand(S,= .Thenδ+(H)≥δ+(D),andsomax{δ+(H),δ (H)}≥k.SinceHisatournament,|S|≥2k+1.Bytheinductionhypothesis,Hcontainsadirectedcycleoflength≥2k+1.
(b)ByTheorem1.5,foranyk(3≤k≤v),everyvertexinTiscontainedindirectedk-cycle.Letx∈V(T)andCbeadirected(v 1)-cyclecontainingxinT.Then,thereisy∈V(T)\V(C)suchthatT yisstronglyconnected.
Ontheotherhand,letC beadirected(v 1)-cyclecontainingyinT.Thenthereisz∈V(T)\V(C )suchthatT zisstronglyconnected.Sincez=y,thesetS={y,z}isrequired.
(c)LetCbeadirectedk-cycle.ThenT[C]isastronglyconnectedtournament.ByTheorem1.5,theassertionistrue.
Ex1.7.6LetP=(x0,x1,···,xk 1,xk)bealongestpathinG.Bycontradiction.Assumek<2δandlet
S={xi:x0xi+1∈E(G)},T={xi:xkxi∈E(G)}.
Then,|S|=dG(x0)≥δ,|T|=dG(xk)≥δandxk∈/S∪T.
FirstprovethatGcontainsacycleoflengthk+1.Sincexk∈/S∪T,then|S∪T|≤k<2δ,andsoS∩T= .Letxi∈S∩T.ThenC=(x0,x1···,xi,xk,xk 1,···,xi+1,x0)isacycleoflengthk+1inG.
SinceGisconnected,v>2δ≥k+1,thusthereareavertexx∈V(G)\V(C)andavertexinC,sayxj(j=0,k)suchthatxxj∈E(G).However,C xixi+1+xxjcontainsalongerpaththanP,acontradiction.Therefore,k≥2δ.
Ex1.7.7LetCbeashortestoddcycleoflengthninG.Assumen≥5andn≥2k+1.LetS=V(C).FromtheproofofExample1.7.5,|(S,)|≤2(v n).Thus,
δ(G)n≤dG(x)≤2ε(G[S])+2(v n)=2n+2(v n)=2v,
x∈S
fromwhichacontradictionisdeducedasfollows:δ(G)≤ 2v
.
Ex1.9.7(a)Bycontradiction.LetGbemaximalcounterexample,thatis,Gisagraphthatsatis esthegivenconditionsbutG+xycontainsaHamiltoncycleforanytwo
2