平面图着色 婚定理1215:任何平面图都可6-着色 证明:(归纳法)(1)n≤7:结论为真 2)设n=k(7)时结论为真.n=k+1时, veV(G,d()≤5.令G=G-V,对G用归 纳假设,G1可6-着色.模仿G1对G着色,与 V相邻的点不超过5个,至少剩1种颜色给V 着色,所以G可6着色.# 《集合论与图论》第25讲
《集合论与图论》第25讲 11 平面图着色 定理12.15: 任何平面图都可6-着色 证明: (归纳法) (1) n≤7: 结论为真. (2) 设n=k(≥7)时结论为真. n=k+1时, ∃v∈V(G), d(v)≤5. 令G1=G-v, 对G1用归 纳假设, G1可6-着色. 模仿G1对G着色, 与 v相邻的点不超过5个, 至少剩1种颜色给v 着色,所以G可6-着色. #
五色定理 定理1216( Heawood,1890):任何平面图 都可5-着色 证明:(归纳法)(1)n5:结论为真 2)设n=k(25)时结论为真.∩=k+1时, veVG,0()≤5.令G1=GV,对G用归 纳假设,G1可5-着色模仿G对G着色, d()<5,或0)1=5但与v相邻的点用了少于 5种颜色时,至少剩1种颜色给V着色 《集合论与图论》第25讲
《集合论与图论》第25讲 12 五色定理 定理12.16(Heawood,1890): 任何平面图 都可5-着色 证明: (归纳法) (1) n≤5: 结论为真. (2) 设n=k(≥5)时结论为真. n=k+1时, ∃v∈V(G), d(v)≤5. 令G1=G-v, 对G1用归 纳假设, G1可5-着色. 模仿G1对G着色, 当 d(v)<5, 或d(v)=5但与v相邻的点用了少于 5种颜色时, 至少剩1种颜色给v着色.
五色定理(续) 《集合论与图论》第25讲 13
《集合论与图论》第25讲 13 五色定理(续) ?
五色定理(续) 证明:(续)当d()=5且与V相邻的点用了5 种颜色时,设v与V相邻且着颜色i,=1, ,5.根据 Jordan定理,下面2种路径不 能同时存在:从v到v3只有{1,3这2种颜 色的路径,从V2到只有24这2种颜色 的路径不妨设在只有{1,3这2种颜色的 顶点的导出子图中,v与3是在不同的连 通分支中,于是把v所在分支里13颜色 互换,然后把颜色1给v.# 《集合论与图论》第25讲
《集合论与图论》第25讲 14 五色定理(续) 证明: (续) 当d(v)=5且与v相邻的点用了5 种颜色时, 设vi与v相邻且着颜色i, i=1, 2,…, 5. 根据Jordan定理,下面2种路径不 能同时存在: 从v1到v3只有{1,3}这2种颜 色的路径, 从v2到v4只有{2,4}这2种颜色 的路径. 不妨设在只有{1,3}这2种颜色的 顶点的导出子图中, v1与v3是在不同的连 通分支中, 于是把v1所在分支里1与3颜色 互换, 然后把颜色1给v. #