nonadjacentverticesx∈X,y∈Y,whereX={x1,x2,···,xn},Y={y1,y2,···,yn}.LetC=(x1,y1,x2,y2,···,xn,yn,x1)beaHamiltoncycleinG+x1y1andlet
I={i:2≤i≤n,x1yi∈E(G)}.
ThenI=NG(x1)andxi 1y1∈/E(G)foranyi∈I.Thus,NG(y1) X\{xi 1:i∈I},andsodG(y1)≤n |I|=n dG(x1),fromwhichacontradictionisdeducedasfollows.dG(x1)+dG(y1)≤n.
(b)From(a),itissu cienttoprovethatdG(x)+dG(y)>nforanytwononadjacentverticesx∈Xandy∈Y.Bycontradiction.Assumethatthereexisttwononadjacentverticesx∈Xandy∈YsuchthatdG(x)+dG(y)≤n.SinceGisbipartiteand|X|=|Y|=n,GcanbeviewedasagraphobtainedfromKn,nbydeletinghedges.Ontheonehand,
h=n2 ε(G)<n2 (n2 n+1)=n 1.
Ontheotherhand,forx∈Xandy∈Y,
h≥[n dG(x)]+[n dG(y)] 1=2n [dG(x)+dG(y)] 1≥n 1.
Thisisacontradiction.
Ex1.10.5(d)LetA =B AandX=(x1,x2,···,xv}beanyvector.Then
T XAX=(xi xj)2≥0,
ij∈E(G)
theequalityholds X=(1,1,···,1).Thus,A semi-positive.
(= )Byinductiononv≥1.Ifv=1,A=O,A =O,andso,rankA =0=1 1.Assumetheassertionholdsforanyconnectedgraphoforderlessthan<v,andletGbeasimpleundirectedgraphoforderv,di=dG(xi)(i=1,2,···,v).Chooseanon-cut-vertexofG(thereareatleasttwosuchverticesbyExample1.5.3).Withoutlossofgenerality,letx1besuchavertexandNG(x1)={x2,x3,···,xd+1}.Therearetwocases.
Case1d1<v 1.Inthiscase,AandtheadjacencymatrixofG x1canbeexpressedas
0J1,d1O1,v d1 1AA1112 ,A11A12A= Jd1,1Av 1=.A21A22Ov d1 1,1A21A22
De netwodiagonalmatricesasfollows.
P1=diag(d2 1,···,dd1+1 1)Id1
Bytheinductionhypothesis,
A v 1= P1 A11 A12
A21P2 A22
3 P2=diag(dd1+2,···,dv)Iv d1 1.T