四色定理的两种证明

发布时间：2010-08-08 20:51:44 来源：文档文库

小中大

字号：

手机查看

同五色定理证明的归纳法

记L[i,j]表示i色和j色交替出现的一条路。

记G[i,j]表示由着i色和j色的顶点的导出子图。

对顶点n做归纳。

1. 当n<=4时，显然可四色着图。

2. 假设当n=k时，可四色着图。于是当n=k+1时，记图中的一个＜=5度的顶点为v。，去掉v。，则剩余k个顶点，根据归纳假设，剩余的k个顶点可用四种颜色着色。

● 当与v。相邻的顶点的着色总数不超过3种时，v。着剩余的第四色。

● 当与v。相邻的顶点的着色总数为4时，有以下两种情况：

(a). d( v。) =4，如图1所示。

图1

图中1，2，3，4代表顶点所着的颜色。当上图中着1，3的顶点之间不存在L[1,3]时，上图中着3的顶点与着1的顶点不在G[1,3]的同一分支中，可将上图中着3色的顶点所在分支中1与3两色调换，于是v。可着3色。当上图中着1，3的顶点之间存在L[1,3]时，着2，4的顶点之间必不存在L[2,4]，同理可将上图中着4色的顶点所在分支中4与2两色调换，于是v。可着4色。

(b). d( v。) =5，必有一种色着了两个顶点。这两个着同色的顶点要么相邻，要么相隔一个顶点（或两个顶点）。不妨设这两个同色顶点都着2色。当这个同色顶点相邻时，如图2所示。证明方法同(a)。

图2 图3

当这两个同色顶点相隔一个顶点（或两个顶点）时如图3所示。若上图中着1，3的顶点之间不存在L[1,3]或着1，4的顶点之间不存在L[1,4]时，证明方法同(a)。上图中着1，3的顶点之间存在L[1,3]且着1，4的顶点之间存在L[1,4]时，被L[1,3]和v。组成的环包围的着2色的顶点与着4色的顶点必不在G[2,4]的同一分支中，于是可将着2色的顶点所在的分支中2与4色调换，使2着4色，同样被L[1,4]和v。组成的环包围的着2色的顶点与着3色的顶点必不在G[2,3]的同一分支中，于是可将这个着2色的顶点所在的分支中2与3色调换，使2着3色，于是v。可着2色。

扩大环着色法

1.在图中找到一个内部没有任何顶点的三角形，三个顶点着三种色。如果没有补充一个，再进行着色。于是构成一个环。

2. 不断将环外的顶点扩到环上，若要扩的顶点仅与环上的一个顶点相连，则将其再与环上另一个顶点相连。在已着色的区域的边界上的顶点相连构成一个环，每扩进一个顶点，调整着色情况，始终保持环上的颜色数不多于3种。此时扩进的顶点最多与三种颜色相连，可着第四种色，然后调整使所成的新环上的颜色数为3种。这样就可4着色。具体方法如下：

A.若新扩入的顶点只与环上的两种颜色相邻，就将此顶点着环上的第三种色。此时新环上仍只存在3种颜色.不必调整。

B.若新扩入的顶点与环上的三种颜色相邻，将此顶点着环上没有的第四种色。此时环上可能已存在4种颜色。不妨设原环上的三种颜色分别为1、2、3。新扩入的顶点着色4。与色4相邻的三色中必然有一种色在环内，不妨设为色1。如下左图所示。

若不存在一条路L[4,1]或这条路中的末端着色l的顶点不在环上，则调换4，1。这样环上就成了1、2、3三种颜色了。若存在一条路L[4,1]且这条路中的末端着色l的顶点在环上，

此时将这条路中的某个顶点v。（不包括这条路的两端的顶点）的着色去掉，则在G[1,4]中，在新扩入的顶点所在的联通分支将4与1色调换。于是环上的颜色就仅为1、2、3三种了，最后再给v。着色。如果有多条这样的L[4,1]，则都照此处理。

下面用归纳法证明v。可用4种颜色中的一种来着色。

当d(v。)<=3时，显然可用4种颜色中剩余的颜色来着色；

假设当d(v。)=k时，v。可用4种颜色中的一种来着色。那么当d(v。)=k+1时，去掉与v。相连的一条边(记去掉的这条边的另一个端点为v'，此时d(v。)=k，由归纳假设可知，v。可用4种颜色中的一种来着色，不妨设v。着色4，其他与v。相邻的顶点除v'外分别着1、2、3中的一种。若v'着色为1、2、3中的一种，则着色完成；若v'着色为4，此时就需调整v'的着色。