设对于小于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色。 100.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色