取v∈V,由于G连通，对任何u∈VUV,G中有 联结u和v的路，故d(,n)有定义。 因为任何一条以为起点的路交替地经过和V,的点， 可知一个点u∈Y当且仅当d(心，u是奇数。这准则唯一地 决定了G的2部划分。 定理2：n阶完全偶图Kml.2的边数m=n1n2,且有： 证明：m=n1n2显然。下面证明第二结论： mK)=K)=(n-%)n= n 4( 5-n2)2s
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 取v∈V1 ，由于G 连通，对任何u∈V1∪V2 ， G中有 联结u 和v的路，故d (v, u)有定义。 因为任何一条以v为起点的路交替地经过V1和V2 的点， 可知一个点u∈V2 当且仅当d (v, u)是奇数。这准则唯一地 决定了G的2部划分。 定理2： n阶完全偶图 Kn1,n2的边数m=n1n2 ,且有： 2 4 n m 证明：m=n1n2显然。下面证明第二结论： 1 2 2 2 2 2 2 , , 2 2 2 ( ) ( ) ( ) ( ) 4 2 4 n n n n n n n n m K m K n n n n − = = − = − −
定理3n阶部图G有最多边数的充要条件是G≌Tm。 证明：首先有： (G)≤m(K,m 其次，考虑： 则f取最大值的充分必要条件为：1i<j≤1，有： n,-n,l≤1 而G的对应的顶点划分形成的1部图正好为T。 从而证明了该定理
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 证明：首先有： 1 2 , , , ( ) ( ) n n nl m G m K 定理3 n阶l部图G有最多边数的充要条件是G ≌ Tl,n。 其次，考虑： 则 f 取最大值的充分必要条件为：1≦i<j ≦l,有: n n i j − 1 而G的对应的顶点划分形成的l 部图正好为T l, n 从而证明了该定理
(二)、托兰定理 定义4设G和H是两个阶图，称G度弱于H,如果 存在双射μ：V(G)→V),使得： v∈V(G),有：dc(v)≤dH(u(v) 注意：若G度弱于H,一定有： m(G)≤m(H) 但逆不成立！例如：(1,1,4,2)与3,3,3,3)没有度弱关系 定理4若阶简单图G不包含K41,则G度弱于某个完 全I部图H,且若G具有与H相同的度序列，则： G兰I
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 (二)、托兰定理 定义4 设G和H是两个n阶图，称G度弱于H，如果 存在双射μ：V(G)→V(H),使得： ( ), ( ) ( ( )) G H v V G d v d v 有： 注意：若G度弱于H，一定有： m G m H ( ) ( ) 但逆不成立！例如：(1,1,4,2)与(3,3,3,3)没有度弱关系！ 定理4 若n阶简单图G不包含Kl+1，则G度弱于某个完 全 l 部图 H，且若G具有与H 相同的度序列，则: G H
证明：对1作数学归纳证明。 当1=1时，结论显然成立； 设对1<t时，结论成立。考虑I=t时的情况。 令u∈V(G),且d(u)=△(G. 设G=GN(川，则G,不含K,否则，G含K+1,矛盾！ 由归纳假设，G,度弱于某个完全t-1部图H1· 又令V1=N(u),V2=V-V1,用G,表示顶点集合为V2的 空图，则G度弱于G,VG,当然度弱于G,VH1。 令H=G,VH,则H是完全t部图。 下面证明定理的第二个结论
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 证明：对 l 作数学归纳证明。 当 l =1时，结论显然成立； 设对 l <t 时，结论成立。考虑l = t 时的情况。 令u ∈V(G), 且d (u) = Δ(G). 设G1= G[N(u)],则G1不含Kt , 否则，G含Kt+1,矛盾！ 由归纳假设，G1度弱于某个完全t-1部图H1 . 又令V1=N (u) , V2=V-V1 , 用G2表示顶点集合为V2的 空图，则G度弱于G2VG1，当然度弱于G2V H1。 令H= G2V H1 ,则H是完全t部图。 下面证明定理的第二个结论