我们证明：上面的着色是正常边着色。 对Km,m中任意的两条邻接边xy,和xyk。若 π(x,y,)=π(xy) 则：i计j(modn=i+k(modn),得到j=k,矛盾！ 所以，上面着色是正常作色。所以： X'(Kmn)≤n 又显然 X'(Kmn)≥△=n ,所以， x'(Kn)=A 例1用最少的颜色数对K3.4正常边着色。 8
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 m, n中任意的两条邻接边xiyj和xiyk。若 ()() i j ik x y x y 则：i+ j ( mod n)=i +k ( mod n),得到j=k，矛盾！ 所以，上面着色是正常作色。所以： , ( ) K n m n 又显然 ，所以， , ( ) K n m n , ( ) K m n 例1 用最少的颜色数对K3,4正常边着色
y2 定义3设T是G的一种正常边着色，若点u关联的边的 着色没有用到色i,则称点u缺i色。 定理2（哥尼，1916若G是偶图，则x'(G)=△ 证明：我们对G的边数作数学归纳。 当m=1时，△=1，有x'(G)=△=1
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 定理2 (哥尼，1916)若G是偶图，则 x x2 1 x0 y1 y2 y3 y0 ( ) G 定义3 设п是G的一种正常边着色，若点u关联的边的 着色没有用到色i，则称点u缺i色。 证明：我们对G的边数m作数学归纳。 当m=1时，Δ=1，有 () 1 G
设对于小于m条边的偶图来说命题成立。 设G是具有m条边的偶图。 取v∈E(G),考虑G=G-Y,由归纳假设有： X'(G)=△(G)≤△(G) 这说明，G,存在一种△(G)边着色方案Ⅱ。对于该着色方案， 因为uv未着色，所以点u与v均至少缺少一种色。 情形1如果u与v均缺同一种色i,则在G,+v中给uv着色 i,而G,其它边，按Π方案着色。这样得到G的△着色方案 所以： x'(G)=△ 情形2如果u缺i色，但不缺j色；而v缺i色，但不缺i色。 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是具有m条边的偶图。 设对于小于m条边的偶图来说命题成立。 取uv∈ E(G), 考虑G1=G-uv,由归纳假设有： 这说明，G1存在一种Δ(G)边着色方案п。对于该着色方案， 因为uv未着色，所以点u与v均至少缺少一种色。 1 1 ( ) ( ) () GGG 情形1 如果u与v均缺同一种色i, 则在G1+uv中给uv着色 i, 而G1其它边，按п方案着色。这样得到G的Δ着色方案， 所以： ( ) G 情形2 如果u缺i色, 但不缺j色； 而v缺j色，但不缺i色
设H(,)表示G,中由色边与j色边导出的子图。显然， 该图每个分支是色边和色边交替出现的路或圈。 对于H(i,j)中含点v的分支来说，因v缺色j,但不缺色i, 所以，在H(i,)中，点v的度数为1。这说明，Hi,j)中含y 的分支是一条路P。 进一步地，我们可以说明，上面的路P不含点u。 因为，如果P含有点u,那么P必然是一条长度为偶数的 路，这样，P+v是G中的奇圈，这与G是偶图矛盾！ 既然P不含点u,所以我们可以交换P中着色，而不破坏 G,的正常边着色。但交换着色后，u与v均缺色i,于是由 情形1，可以得到G的△正常边着色，即证明：x(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 11 设H (i, j) 表示G1中由i色边与j色边导出的子图。显然， 该图每个分支是i色边和j色边交替出现的路或圈。 对于H(i, j)中含点v的分支来说，因v缺色j, 但不缺色i, 所以，在H(i, j)中,点v的度数为1。这说明，H(i ,j)中含v 的分支是一条路P。 进一步地，我们可以说明，上面的路P不含点u。 因为，如果P含有点u, 那么P必然是一条长度为偶数的 路，这样，P+uv是G中的奇圈，这与G是偶图矛盾！ 既然P不含点u, 所以我们可以交换P中着色，而不破坏 G1的正常边着色。但交换着色后，u与v均缺色i, 于是由 情形1,可以得到G的Δ正常边着色，即证明：( ) G