HintstoExercisesinChapter5
Ex5.1.1Withoutlossofgenerality,assumeGisconnected.Clearly,α (G)≤ 1 .21 Wenowshowα(G)≤ byinductiononε≥1.Assumeε(G)=k+1≥2.IfGcontainsacycleC,thenchooseanedgeeinC.Bytheinductionhypothesis,
vv≥.α(G)≥α(G e)≥ (G e)1+ (G)
IfGcontainsnocycle,thenGisatree.IfGisastar,thentheconclusionholdsclearly.AssumeGisnotastarbelow.Thus,thereisanedgeeinC.LetG1andG2betwocomponentsofG e,andletvi=v(Gi)foreachi=1,2.Bytheinductionhypothesis,
α (G)≥α (G1)+α (G2)≥v1v2v1+v2v+≥=. (G1) (G2)1+ (G)1+ (G)
2
Ex5.1.3Notethatthisexercisehasanerratum,thatis,2
vshouldbereplacedbyε.
LetGbeaplanetriangulationoforderv(≥4).Bytheexercise4.3.8,G isa3-regular2-edge-connectedsimplegraph.ByCorollary5.2.1,G hasaperfectmatchingM .GisconnectedsinceGaplanetriangulation.Thus,bytheexercise3.3.1,(G ) ～=G,andso(G M ) isisomorphictosomesubgraphofG.ByEuler’sformula,
ε(G M )=ε(G ) 1 3 1 v=v v=v =φ=2+ε v.222
1SinceGisaplanetriangulation,byTheorem3.4,ε=3v 6,thatis,v=ε+2.It
followsthat12ε(G M )=2+ε v=2+ε ε 2=ε.33
Notethat(G M ) isequivalenttoagraphobtainedfromGremovingsomecommonedgesintwotriangles.Thus,G M containsonlycyclesoflengthfour,henceisbipartite.Thus,Gcontainsabipartitesubgraphwith2εedges.Ex5.1.6ByTutte’stheorem,o(G x)≤1foranyx∈V(G).Ifthereisavertexxsuchthato(G x)=0,thenGhasoddorder,acontradiction.
Conversely,byinductiononv≥2.LetGbeatreeoforderv≥3.ChooseavertexxofdegreeoneinG.Sinceo(G x)=1,viseven.Letybetheuniqueneighborofx.Sinceo(G y)=1,{x}istheonlyoddcomponentofG y,andothercomponentsG1,G2,···,Gpareeven.Theno(Gi z)=1foranyz∈V(Gi)andeachi=1,2,···,p(Why?).Bytheinductionhypothesis,GihasperfectmatchingMiforeachi=1,2,···,p.ThenM=Mi∪M2∪···∪Mp∪{xy}isaperfectmatchingofG.Ex5.1.10Byde nitionsofpermanentA=(aij)m×nandPer(A),
Per(A)=a1f(1)a2f(2)···amf(m),
f∈F
9