四色定理的简要证明

《四色定理的简要证明》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、四色定理的简要证明：文章严格遵循数学归纳法步骤，利用数学归纳法和平面图的一个定理成功证明了世界近代三大数学难题之一的四色定理，并献疑于该定理的“计算机证明”。　　关键词：数学归纳法；证明；平面图；四色定理　　：G633.6：A：1002-7661（2011）11-045-01　　　　　　“画地图要求相邻两国不用同一色，一幅地图只需要四种颜色”（钱学森语），这就是著名的“四色定理”（或称“四色问题”）。自1872年正式提出至1976年才被计算机证明，但这“机证”并非让所有人信服。下面给出一种非“机证”的简洁的理论证明。　　一、相关前提　　前提1任

2、何平面地图的着色问题可以转化、归纳为对平面图的结点的着色问题。其中的结点代表地图上的国家（或地区，下同），结点间的连线即边代表国家间的相邻关系。　　前提2着色规则——平面图内有连线（即边，下同，为叙述方便会交替使用）的点（即结点，下同）必须用不同种的颜色着色，而没有连线的点则肯定可以用同一种颜色着色。　　前提3“正常着色”是指遵守“前提2”所称着色规则的着色。　　前提4设G是有v个结点e条边的连通简单平面图，若v>=3，则e=3），都适用e=5）时，定理成立，即可用4种色对图G(k)正常着色，亦即可用4色对k个结点正常着色。　　那么，当n=k1

3、时，对这（k1）个结点着色，必定可分两步进行：　　第一步，首先对其中的k个结点着色；　　第二步，才对剩下的“1”个结点（称为第n点，n=k1）着色。已知k个点可用4色正常着色，不难证明第n点也可以用这4色中的某一色正常着色。其理由是：　　当n=k时，图G(k)共有结点个数为：v(k)=k(a)；边数据“前提4”为：　　e(k)<=3v-6=3k-6(b)　　当n=k1时，有图G(k1),此时　　G(k1)的结点个数为：v(k1)=k1(c);边数则为:e(k1)<=3v-6=3(k1)-6=(3k-6)3(d)　　因为：(c)-(a)=(k1)

4、-k=1,(d)-(b)<=(3k-6)3-(3k-6)<=3　　所以可确知：图G(k1)比图G(k)仅增加1个结点(即第n点)及最多增加3条边，所增加的3条边是增加的第n点所引致，两者具有对应关系。所以对图G(k1)着色可以转化为：对G(k)着色与对新增加的1个结点（即第n点）着色。　　显然，G(k)据题设(2)用4色可正常着色；而对第n点则可用G(k)正常着色时用过的4色中的某一色正常着色，因为：第n点最多对应3条边，即这点最多与原图G(k)中的3个结点（简称3色点）连线、相邻，不可能再与G(k)中的其它结点连线、相邻.根据着色规则，“3色

5、点”最多着3色(称为3点色)，第n点不能用这“3点色”着色；但既然G(k)用4色可正常着色，那么这4色中必有有别于“3点色”的另1色，称为“第4色”，因为第n点只与“3色点”相邻，不与G(k)中着“第4色”的任何结点相邻，所以它必定可以用“第4色”正常着色！　　这样，既然G(k)可用4色正常着色，而第n点又可用图G(k)4色中的“第4色”正常着色，那么由这二者“组成”的图G(k1)理所当然可用4色正常着色,亦即全部（k1）个结点可以用4色正常着色。　　根据（1）、（2）可以知道，对于平面图G(n)(n为自然数)的所有n个结点进行正常着色，4色就

6、足够，即四色定理成立！　　三、对“机证”献疑　　根据“e<=3v-6”可知，v个结点的平面图肯定比(v-1)个结点的平面图多1个结点[称为第v点，在G(v-1)的最外面，亦即G(v)的最外面]和3条边。所以实际画有v个结点的平面图G(v)时，理应画出最外面的第v点，它只与3条边相连。任何e=3v-6(取最大值)的平面图都必定如此.但很遗憾，在四色定理“机证”所依据的“构形”图中（显然构形的e也取最大值），没有发现这个特征。所以“机证”所依据的“构形”是令人可疑的，因而所进行的一系列证明过程与结果也都是令人可疑的。　　参考资料　　[1]徐俊明.图

7、论及应用[M].中科大出版社（合肥）,1998:305~309.　　[2]哈拉里（美）.图论第一版[M].上海科技出版社,1980:145~166.　　[3]张忠辅.数学的陷阱——四色猜想的各种“证明”[J],上海自然杂志,1992:380~381.