(2)对于G,来说，G,的任意3正常着色方案导出的顶点 划分均是{(v},(v2,v4}v3Vs)),所以，G2是 唯一3可着色图；例如： 毛露裙 (3)对于G3来说，G3不是唯一3可着色图；因为： VI
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 11 v1 G2 v5 v3 v4 v2 (2) 对于G2来说，G2的任意3正常着色方案导出的顶点 划分均是｛｛v1｝, ｛v2，v4｝｛v3 ,v5｝｝，所以，G2是 唯一3可着色图；例如： v1 G2 v5 v3 v4 v2 v1 G2 v5 v3 v4 v2 (3) 对于G3来说，G3不是唯一3可着色图；因为： G3 v5 v4 v3 v2 v1 G3 v5 v4 v3 v2 v1
下面给出唯一可着色图的几个特征。 定理2（哈拉里，1968）设G是唯一k可着色图，k心2，则： (1)8≥k-1; (2)在G的任意一种k着色中，G的任意两个色组的并的 导出子图是连通的。 证明：(1)若不然，设δ<k-1,令d(u=δ，则 kuUW(u)≤k-1 N(U) 12
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 12 下面给出唯一可着色图的几个特征。 定理2(哈拉里，1968）设G是唯一k可着色图，k≥2, 则： (1) δ≥k-1; (2) 在G的任意一种k着色中，G的任意两个色组的并的 导出子图是连通的。 证明： (1) 若不然，设δ< k-1, 令d(u) =δ,则 u N u k ( ) 1 − u N (u)