复旦大学：《离散数学》课程教学讲义（图论）第八章 图的基本概念

>证明方法: 由握手定理可知,必要性是显然的。 采用构造性方法进行充分性证明

 证明方法：  由握手定理可知，必要性是显然的。  采用构造性方法进行充分性证明

>充分性证明:d=(dl,d2,……,adn)中有偶数个奇数, 设奇数个数为2k0式m/2,奇数分别为d1ndl2,…, d1k+t…,dl2,用如下方法构造无向图G/,E), v,V2…,vn}。首先在顶点v和v+之间连边{vn ir+/s r=,2,…,k。若d为偶数,令d1’=l;若d 为奇数,令d1=d-1;得d’=(a1;d2 则d120且为偶数。再在v处作d2条环,i=1, 2,……,n,将所得边集合在一起组成边集E,则 G(V,E)的度数列为d >所以d=(dh,d2……,dn)是可图化的

 充分性证明：d= ( d 1, d2, ……, dn )中有偶数个奇数， 设奇数个数为2k(0 k[n/2])，奇数分别为 di1, di2, …, dik, dik+1, …, di2k，用如下方法构造无向图G(V, E) ， V={v 1, v 2,…, v n}。首先在顶点 vir 和 vir+k之间连边 { vir, vir+k } ，r=1, 2, …, k。若 di为偶数，令 di’= di；若 di 为奇数，令 di’= di-1；得d’= ( d 1’, d2’, ……, dn’) 。 则 di ’0且为偶数。再在 vi处作 di’/2条环，i=1, 2,……, n，将所得边集合在一起组成边集 E，则 G(V, E)的度数列为 d 。  所以d= ( d 1, d2, ……, dn )是可图化的

定理B 设非负整数列d=(d 1x22……xn0,则d可简单图化当且仅当对 于每个整数r,ss(mn-1) ∑d,sr(r-1)+∑ minr. a dH且∑d1=0(mod2)

 定理B 设非负整数列d=(d1, d2, ……, dn)，(n- 1)d1d2……dn0，则d可简单图化当且仅当对 于每个整数r, 1r(n-1) 1 1 ( 1) m in { , } 0(mod 2) r n i i i ir d rr rd        n i i=1 且 d

>定理C 设非负整数列d=(01x…过n20,则可简 =0m0d2)且mn-1)212d2 单图化当且仅当 d1+2 是可简单图化的

 定理 C 设非负整数列d=(d1, d2, ……, dn) ， di=0(mod 2) 且(n-1) d 1 d2 …… dn 0，则 d可简 单图化当且仅当 是可简单图化的。 1 1 23 1 2 ' ( 1, 1,......, 1, ,......, ) dd n dd d d d d     

>证明: >充分性证明:因为d是可简单图化的,设G1,E) 是以d为度数列的简单图。V={,v2…,vn}。 d-1,i=2,3,…,4+l d1+2cd1+3…

 证明：  充分性证明：因为d’是可简单图化的，设G’(V’, E’) 是以d’为度数列的简单图。V’={v 1, v 2, …, v n} 。 1 ' 1 1 1, 2,3,......, 1, ( ) , 2, 3,......, . i G i i di d d v d id d n        