五色定理的简捷证明

早在1890年 P.J.Heawood 利用 A.B.Kempe 方法证明了五色定理,本文将提出一个较简捷的证明.定义在图 G 的一个着色方案中,分别着 a,b 颜色的点以及它们之间的边所构成的子图G_(ab)可能是连通的,也可能是不连通的.若分别着 a,b 色的点 vi 和 vi 在 G_(ab)的不同连通片中,则 v_i 和 v_j 之间不存在 a、b 两色交错路径,那末把 v_i 着为 a 色或改着 b 色不会影响v_j 的着色.此时,v_i 和 v_j 被称为不相干点对,记为(v_i;v_j).引理可五着色平面图 G 中任意5个点 v_1,v_2,v_3,v_4,v_5分别用 a,b,c,d,e 色着色