Theorem 2.6 Let r and n be integers with 0srs n-1.There exists an r-regular graph of order n if and only if at least one of r and n is even. U1 U10 1,为什么r和n都是奇数时，这个图不可能是r-regularl的？ 9 U3 U 2,当r或者n中有一个为偶数时，构造r-regular图 6 U5 First,assume that r is even.Then r=2k sn-1 for some nonnegative integer ks(n-1)/2.For each i(1sisn),we join vi to vi+ +2..vi+k and to vi-1,vi-2....vi-k If we think of arranging the vertices vv2 ...ncyclically,then each vertex v is adjacent to the k vertices that immediately follow and the k vertices that immediately precede vThusH is r-regular.1，为什么r和n都是奇数时，这个图不可能是r-regular的？ 2，当r或者n中有一个为偶数时，构造r-regular图