例3求证：仅有的1临界图是k;仅有的2临界图是K2；仅 有的3临界图奇圈。 证明：由于1色图是空图，所以1临界图只能是K:2色 图是偶图，所以，2临界图只能是K2；3色图必然含有奇圈， 而奇圈的色数是3，所以，3临界图只能是奇圈。 例4求证：布鲁克斯定理等价于下述命题：若G是k临 界图k②4)，且不是完全图，则2m≥nk-1)+1,其中m为G的 边数而n为顶点数。 证明：(1)由布鲁克斯定理推例4中命题。 因G是k临界图，所以G是连通单图，又k≥4，所以G不能 是奇圈，再由G不是完全图，所以由布鲁克斯定理有
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 例3 求证：仅有的1临界图是k1;仅有的2临界图是K2;仅 有的3临界图奇圈。 证明：由于1色图是空图，所以1临界图只能是K1;2色 图是偶图，所以，2临界图只能是K2; 3色图必然含有奇圈， 而奇圈的色数是3，所以，3临界图只能是奇圈。 例4 求证：布鲁克斯定理等价于下述命题：若G是k临 界图(k≥4), 且不是完全图，则2m≥n(k-1)+1,其中m为G的 边数而n为顶点数。 证明：(1) 由布鲁克斯定理推例4中命题。 因G是k临界图,所以G是连通单图，又k≥4, 所以G不能 是奇圈，再由G不是完全图，所以由布鲁克斯定理有
k至△。 再由k临界图的性质，有δ≥k1.所以： 2m= ∑d(v)≥△+(n-1)δ vEV(G) ≥k+(n-1)(k-1) =n(k-1)+1 (2)由例4中命题推布鲁克斯定理。 因为连通单图G不是奇圈，也不是完全图。设G的k临 界子图是H。 情形1，H是奇圈。 在这种情况下，由于G不是奇圈，所以，H之外必然 有边和H相连，即△(G)≥3，另一方面，k(G)=k(H)=3,所
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 k≦Δ。 再由k临界图的性质，有δ≥k-1.所以： ( ) 2 ( ) ( 1) vVG m dv n kn k ( 1)( 1) n k( 1) 1 (2) 由例4中命题推布鲁克斯定理。 因为连通单图G不是奇圈，也不是完全图。设G的k临 界子图是H。 情形1， H是奇圈。 在这种情况下，由于G不是奇圈，所以，H之外必然 有边和H相连，即Δ(G)≥3,另一方面，k(G)=k(H)=3,所
以，k(G)至△(G); 情形2，H是完全图HK 在这种情况下，由于G是连通的非完全图，那么在H 之外，必然有边和H相连，即△≥K()=k(G): 情形3，H既不是奇圈又不是完全图，由例3知道， k≥4。H满足例4中条件。 所以，由例4中的结论有： △(H)n(H)≥2m(H)≥n(H)(k(H)-1)+1 =n(H)(k(G)-1)+1 所以，有： △(H)≥(k(G)-1)+ n(H
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 以，k(G)≦Δ(G); 情形2， H是完全图HK 在这种情况下，由于G是连通的非完全图，那么在H 之外，必然有边和H相连，即Δ≥K(H)=k(G); 情形3， H既不是奇圈又不是完全图，由例3知道， k≥4。H满足例4中条件。 所以，由例4中的结论有： ( ) ( ) 2 ( ) ( )( ( ) 1) 1 HnH mH nH kH nH kG ( )( ( ) 1) 1 所以，有： 1 ( ) ( ( ) 1) ( ) H kG n H
即证明： △(G)≥k(G) 2、唯一可着色图 对图的顶点进行正常着色，实际上给出图的顶点集合的一 种划分，不同的着色方案，给出的划分一般不同。但是，也 存在一类特殊图，对于任意的最优着色方案，导出的顶点划 分却是相同的。为此，我们给出如下定义。 定义2设简单标定图G的点色数是k,如果在任意的k正 常点着色方案下，导出的顶点集合划分唯一，称G是唯 一k可着色图，简称唯一可着色图。 10
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 10 即证明： () () G kG 2、唯一可着色图 对图的顶点进行正常着色，实际上给出图的顶点集合的一 种划分，不同的着色方案，给出的划分一般不同。但是，也 存在一类特殊图，对于任意的最优着色方案，导出的顶点划 分却是相同的。为此，我们给出如下定义。 定义2 设简单标定图G的点色数是k, 如果在任意的k正 常点着色方案下，导出的顶点集合划分唯一，称G是唯 一k可着色图，简称唯一可着色图