>在G中增加一个新顶点v,使v与v,V an+均相邻,设所得新图为G。在G中 d(v)=a,i=,2,,n,即G以d为度数列,这 说明d是可简单图化的
在G’中增加一个新顶点 v 1，使 v 1 与 v 2, v 3, …, vd1+1均相邻，设所得新图为 G。在 G中， d G(v i)=di ，i=1,2,…,n，即 G 以 d为度数列，这 说明 d是可简单图化的
>必要性证明:设G是以d为度数列的简单图,分两 种情况: (1)在G,E)中,若存在veV,v与度数为d2 d3……,d+的d1个顶点均相邻,在G中去掉v及其 v所关联的一切边,设所得图为G’,则G以 d'=(d2-1,d3-1,,d +2 du) >为度数列,这正说明d是可简单图化的
必要性证明：设G是以d为度数列的简单图，分两 种情况： （1）在G(V, E)中，若存在vV，v与度数为d2, d3, ……, dd1+1的d1个顶点均相邻，在G中去掉v及其 v所关联的一切边，设所得图为G’，则G’以 为度数列，这正说明d’是可简单图化的。 1 1 23 1 2 ' ( 1, 1,..., 1, ,..., ) ddn dd d d d d
(2)G中不存在与度为d2d3……,dm+的顶点均相邻的度 数为d1的顶点。 在G中,设d(v)=d,并设v是所有度数为d的顶点中,其邻 域中顶点度数之和最大的顶点,由G的性质可知,必存在 度分别为dd2d顶点v"而(,vE,vveE。,因 为d→d,因而存在,(v,vE,(1,vE。在G中去掉 边,V)和',v,加新边v,v和 得图设为G 则da/()=d"),i=1,2,n,G1的度数列依然是d=(d2 ·· 并且v在G中所邻顶点度数之和不会小于 在G中所邻顶点的度数之和。对G重复上述过程,直到得 到图G,它有一个顶点v1与度为d2d3,……,d+的顶点均 相邻。在G中删去v1及关联的一切边,所得图G,则G以 d=(d2-1,d3 2 为度数列,所以d'是可简单图化的
（ 2 ） G中不存在与度为 d2, d3, ……, dd1+1的顶点均相邻的度 数为 d1的顶点。 在 G中，设d(vi)=di，并设 vi是所有度数为 d1的顶点中，其邻 域中顶点度数之和最大的顶点，由 G的性质可知，必存在 度分别为 di, dj(di>dj )顶点 vi, vj，而 (vi, vj ) E，(v 1, vj ) E。因 为 di>dj，因而存在 v k，(vi, v k) E，(v 1, v k) E。在 G中去掉 边 (v 1, vj ) 和 (vi, v k)，加新边 (v 1, vi ) 和 (vj, v k)，得图设为 G 1， 则 dG1(vi)= d G(vi )，i=1, 2, …, n，G 1的度数列依然是d=(d1, d2, ……, dn)，并且 v 1 在 G 1中所邻顶点度数之和不会小于它 在 G中所邻顶点的度数之和。对 G 1重复上述过程，直到得 到图 G r，它有一个顶点 v 1与度为 d2, d3, ……, dd1+1的顶点均 相邻。在 G r中删去 v 1及关联的一切边，所得图 G r’，则 G r’以 为度数列，所以d’是可简单图化的。 1 1 23 1 2 ' ( 1, 1,..., 1, ,..., ) ddn dd d d d d
例:利用定理C判断下列两个非负整数列是 否是可简单图化的 (1)(5,5,4,4,2,2) >(2)(4,4,3,3,2,2)
例：利用定理C判断下列两个非负整数列是 否是可简单图化的。 (1) (5, 5, 4, 4, 2, 2) (2) (4, 4, 3, 3, 2, 2)
>(1)(5,5,4,4,2,2) >(4,3,3,1,1) →(2,2,0,0) >(1,-1,0) 显然(2,2,0,0)不可简单图化,所以(5, 5,4,4,2,2)不是可简单图化
(1) (5, 5, 4, 4, 2, 2) (4, 3, 3,1,1) (2, 2, 0, 0) (1, -1, 0) 显然(2, 2, 0, 0)不可简单图化，所以(5, 5, 4, 4, 2, 2) 不是可简单图化