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

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

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