HintstoExercisesinChapter2
Ex2.1.2Theassertion(c)canbeprovedstructurally.
Ex2.1.3v1=v3+2v4+···+( 2)v +2=2+
i=3(i 2)vi=2+ x∈U(dG(x) 2).
Ex2.1.4Therearesomewrongsinthisexercise.Itshouldbecorrectedas“Provethatif{X,Y}isabipartitionofTwith|X|=|Y|=k,thenthereareatleast(k+1)verticesofdegreeoneinX.”Byinductiononk≥0.
Ex2.1.15SinceanytwospanningtreesofXhavethesamenumberofedges,thesymmetricdi erenceoftheiredgesetsiseven,say2m.ToprovethatT(X)isconnected,itissu cienttoshowthatanytwospanningtreesofX,astwovertices,areconnectedinT(X).Wecandothisbyinductiononm≥1.Ifm=1,then,bythede nitionofT(X),thetwospanningtreesareadjacentinT(X),andsoareconnected.AssumeanytwospanningtreesofXareconnectedinT(X)ifthesymmetricdi erenceoftheiredgesetsislessthan2m.
LetTandT betwospanningtreesinXthatthesymmetricdi erenceoftheiredgesetsis2mwithm≥2.letE1=E(T)\E(T )andE2=E(T )\E(T).Then|E1|=|E2|=m.SinceT isaspanningtreeofX,foranedgee∈E1,T +econtainsonlycycle,denotedbyCe.SinceT containsnocycle,thereexistsexactlyoneedgee ∈E2∩E(Ce)suchthatT =T e +eisaspanningthreeofX.Itisclearthatthesymmetricdi erenceofE(T )andE(T )is2,andthus,theyareadjacentinT(X).Also,thesymmetricdi erenceofE(T)andE(T )is2(m 1),andthus,bytheinductionhypothesis,theyareconnectedinT(X).ItfollowsthatTandT areconnectedinT(X).Ex2.3.2SeeExample1.10.2.
Ex2.3.3Theproofsof(a)and(b)aresimilartoExample2.3.2.As(c),ifGisnotbipartite,thenGcontainsanoddcycle.LetCbeashortestoddcycle.Thedeterminantofthesub-matrixofMrespondingtotheverticesandedgesinCisequaltotwo,acontradiction.Conversely,byinductiononk≥1,whichisorderofasub-matrixofM.Intheinductionstep,assumeP +1isasub-matrixofM.Ifthereisexactlyonenon-zeroentryinsomecolumn,thenitiseasytoprovedetP +1=0,±1.Assumethereareexactlytwonon-zeroentriesinP +1below.ItisclearthatdetP +1=0sincethesumofanycolumnistwo.
Ex2.3.6Foreachvertexy=x,selectonein-comingedgeofy.LetTbetheinducedsubgraphbytheseedges.ThenTisanin-treerootedatx,forThasv 1
edges,containsnodirectedcycles,d T(x)=0,dT(y)=1foranyy=x(seeExercise
2.1.1).Conversely,everyin-treerootedoccursinthisway.Hencethenumberof atx
suchin-treesrootedatxis x(G)=d G(y).
y∈V\{x}
5