请教一道组合数学题

(i)((1))根据对称性只需证明:G的任两个不相邻的顶点x和y,则d(x)≤d(y).设x和a1,..am相邻,其中m=d(x),且y和a1相邻,则显然有y和a2,..am不相邻.((2))可设a2为x和a1的公共邻点,b2为y和a1的公共邻点,则a3,..am和a1,a2,b2不相邻.比如有as,3≤s≤m,as和a1相邻,==>as和a2为x和a1的公共邻点和唯一性矛盾.((3))根据题意有b3,..bm分别为y和a3,..am的公共邻点.若有3≤i<j≤m,bi=bj,则x和bi为ai和aj的公共邻点和唯一性矛盾.所以b3,..bm各不相同,而根据((2))得:x的邻点a1,b2,b3,..bm各不相同,所以x的邻点至少有m个==>d(x)≤d(y).同理可得:d(y)≤d(x).==>d(y)=d(x).(ii)((1))由于任意顶点x,d(x)≤n-2==>有顶点y和x不相邻,根据(i)得:d(x)=d(y).((2))由于只有顶点a为x和y的公共的邻点,所以G的其他顶点z和x或y不相邻==>d(z)=d(x)=d(y).==>除a以外的顶点的次都相等.((3))d(a)≤n-2==>有顶点b和a不相邻==>d(a)=d(b)所以G的所有顶点的次都相等,即G是正则图. 收起