whereF={f:fisaninjectivefrom{1,2,···,m}to{1,2,···,n}},and|F|=n(n 1)···(n m+1).LetX={x1,x2,···,xm}andY={y1,y2,···,ym}.Ifa1f(1)a2f(2)···amf(m)=0,thena1f(1)a2f(2)···amf(m)=0denotesthatthesetofedges
EG(x1,yf(1))= ,EG(x2,yf(2))= ,···,EG(xm,yf(m))= .
Thus,a1f(1)a2f(2)···amf(m)isthenumberofthematchingsthatsaturateXandconsistofedgedinthesetofedges
EG(x1,yf(1))∪EG(x2,yf(2))∪···∪EG(xm,yf(m)).
ItfollowsthatthenumberofthematchingsthatsaturateXisequaltoPer(A).
Ex5.2.5(a)ByTheorem5.6,itissu cienttoshowα(G)≤κ(G).Bycontradic-tion,ifα(G)>κ(G)=k,thenthereisanindependentsetIsuchthat|I|=k+1.A¯I)|≤k2<k(k+1)=|(I,I¯)|.contradictioncanbededuceasfollows.|(I,
(b)TheproofissimilartooneofTheorem5.7.Sinceα(G)=1ifandonlyifG～=Kv,assumeα(G)≥2.ChoosealongestcycleCinG.SupposetothecontrarythatCisnotaHamiltoncycle.Then,V(G)\V(C)= andT V(C).Choosex∈V(G)\V(C)andletT={x1,x2,···,xs}andoccursinCinthisorder.BythechoiceofC,anysuccessivetwoverticesin{x1,x2,···,xs}arenotadjacentinC,otherwisewecanconstructalongercyclethanC.→ SpecifyCadirectiontoobtainedadirectedcycleC.LetY={yi:(xi,yi)∈→ E(C),i=1,2,···,s}.ThenY∪{x}isanindependentsetofGandα(G)≥|I|=s+1≥|T|+1,contradictingtothehypothesis.
Ex5.2.6TheproofissimilartooneofTheorem5.7.Withoutlossofgenerality,assumeα(G)≥2.Bycontradiction,assumeα≥δ(G)+1.LetIandSbeamaximumindependentsetandaminimumseparatingsetofG,respectively.Then,foranyx,y∈I,wehave|NG(x)∪NG(y)|≤v α,and
|NG(x)∩NG(y)|=dG(x)+dG(y) |NG(x)∪NG(y)|
≥2δ (v α)≥3δ v+1≥κ+1>|S|.
ThisimpliesthatonlyoneofallcomponentsofG S,sayG1,maycontainverticesinI,thatis,I V(G1)∪S.Sinceα≥2δ+1,thereexistsx∈I∩V(G1).Chooseavertexzinothercomponent,sayG2,ofG S.Then
|NG(x)∪NG(z)|≤v 2 |I∩V(G1)|+1=v α+|I∩S| 1.
SinceNG(x)∩NG(z) S\I,thus,|NG(x)∩NG(z)|≤κ |I∩S|.Thus,weshouldhavethat
2δ≤dG(x)+dG(z)=v α+κ 1≤v+κ δ 2.
11(v+κ 2)<(v+κ).Fromthiswecandeduceacontradictionasfollows.δ≤Ex5.2.7Notethatthisexercisehasanerratum.Theexerciseisrestatedasfollows.LetGbealooplessdigraph.ProvethatGcontainsanindependentsetIsuchthatdG(I,y)≤2foranyy∈V(G)\I,wheredG(I,y)=min{dG(x,y):x∈I}.
10