关于四色定理的两个定理

一 四色定理

每一幅正规地图（每个国家连成一片；两个国家的共同边界是条线，而不是一点或一些孤立的点；没有一个国家包围其它国家，也没有三个以上的国家相遇一点），至多需要四种色，能使相邻（有共同边界）的国家着不同色。

二 背景简介

1976年，美国专家借助计算机证明了四色定理。但从1852年问世至今，尚未获得纯数学理论的证明。

三 肯普定理

每一幅正规地图，至少有一国具有两个、三个、四个或五个邻国，不存在每一国都有六个或更多邻国的正规地图。

四 定义 定理

定义1：根据肯普定理，称每一国的邻国个数都不小于n（含n。n取2、3、4、5）的正规地图为n构形。

据此，正规地图可分为二构形、三构形、四构形或五构形等四种情形。

定义2：若一国或连成一片的几国被一些国家（至少两个）包围，则称由这些国家形成的环为圈。

定理1：五构形的国家个数的集合W＝｛12,14,15，16，…,n,…｝。

证：为得到集合W，可构造无穷多“两圈型”五构形（内圈包围一国或两国，外圈外部为一国，两圈上的国家个数相等且每一国的邻国个数都是五）。在类似于图一的五构形中，内圈包围P国，外圈外部只有一国，两圈上的国家个数相等，它们可取数列6，7，8，…，m，…⑴中的同一项，这就得出了国家的个数由不小于14的偶数组成数列14，16，18，…,2（m+1）,…⑵，即1→m→m→1（m∈N，m≥6，由内到外。以下同此）；将得出的国家个数相对应的图中的P国恰当地一分为二（因数列⑴中的各项都不小于六，可使得分成的两国每一国的邻国个数各不小于五。如图一中的虚线将P一分为二），又得出了国家的个数由不小于15的奇数组成数列15，17，19，…，2m+3,…⑶，即2→m→m→1。合并数列⑵、⑶及12就得到了所有五构形的国家个数的集合W=｛12,14,15，16，…,n,…｝。易验证1、2、3、…、11、12、13 中只有12存在五构形。

五构形的所有结构即相邻关系并非完全如上。除12外，每一个n∈W，至少与一个“两圈型”五构形对应。W中的每个n所对应的五构形不同结构的个数及复杂程度无论如何，都可视为由“两圈型”五构形演变而成。

定理2：在n≥15的五构形中，若Q的五个邻国满足：ⅰQ被五个邻国形成的圈包围；ⅱ五个邻国中两两相邻的组数是五；ⅲ五个邻国中不存在两国与Q形成圈；ⅳ五个邻国中至少有一国P的邻国个数不小于六，则四色定理成立。

证：若五构形每一国的邻国个数都是五，由欧拉公式（V－E＋F＝2）易知n=12。据此，当n≥14时，至少有一个有五个邻国的Q，在这五个邻国中也至少有一国的邻国个数不小于六。根据定理1，对n（≥15）作数学归纳法。

⑴当n=15时，只有图二1、2、3所示的三种情形，图中各层次（含圈）国家的个数由内到外各依次为一五六三，一五七二及一六六二。如图二1，Q与P都满足定理2的条件。操作如下：首先把相邻的A和Q视为国E（B由五个邻国变成了四个邻国，P由六个邻国变成了五个邻国，其余国家的邻国个数未变，但变成了四构形）；其次至多用四种色，使得四构形在不相邻的P和C（P与A相邻，C与A不相邻）着同色时相邻的国家能着不同色，如P-1、C-1、E-3、B-2、D-2（P着色1。1、2、3、4为色码，不会混淆），其余国家的着色如图所示，即四色定理成立；最后将Q换成色4（其它国家的着色不变，以下同此），则四色定理也成立。如图二2，同样，首先把相邻的A和Q视为国E（B、P都由六个邻国变成了五个邻国，其余国家的邻国个数未变，还是五构形）；其次至多用四种色，使得五构形在不相邻的P和C（P与A相邻，C与A不相邻）着同色时相邻的国家能着不同色，如P-1、C-1、E-3、B-2、D-2，其余国家的着色如图所示，即四色定理成立；最后将Q换成色4，则四色定理也成立（E的邻国个数是六。对图二3类似可证，如图，略）。

⑵假设15≤n≤k时，四色定理都成立，如图三，不妨PBCDAQ依次着色是121234。即是说，在Q和P都满足定理2的条件下，假设都是按上述三个步骤操作模式的方法着色，把A和Q视为国E（PBCDE依次着色是12123），显然D、P、E的邻国个数分别不小于四、五、六，其余国家的邻国个数未变，国家的个数满足14≤n≤k－1，除14外的每一个n值，都含有A和Q未合并与合并后的两种情况，前者为五构形，后者为四构形或五构形。至多用四种色，使得每一个n值所对应的四构形或五构形在不相邻的P和C（P与A相邻，C与A不相邻）着同色时相邻的国家能着不同色，不妨P-1、C-1、E-3、B-2、D-2（P着色是1。若B与D异色，则与归纳假设相悖。比如B-4，由n=k－1〔A和Q视为E，而不是A和Q未合并〕时四色定理成立，但不能还原n=k时四色定理成立），即四色定理都成立（换色前）。把Q换成色4，四色定理也都成立。

当n=k+1时，如图四，取一个有五个邻国的Q，使Q的邻国中至少有一国P的邻国个数不小于六。把A、B与Q视为国E，则 E的邻国个数不小于七，P、C、D的邻国个数都不小于四。其余国家的邻国个数未变，此时n=k－1（利用合并后），其构形为四构形或五构形。根据换色前的归纳假设，四色定理成立，且不相邻的P和C（P与A相邻，C与A不相邻）着同色，不妨P-1、C-1、E-3、D-2。把Q换成色4，四色定理也成立。证毕。

附：证明四色定理的一个思路

视正规地图中所有的国家连成一片（否则对每一片做同样的证明），分为这一片内部没有空的区域（这时视正规地图的内部与外部的分界线为正规地图的边界）和有空的区域（存在没有包围国家的圈）。把每个空的区域各视为一国，后者就转化成了前者，若这时四色定理成立，把空的区域所着的色去掉，还原出原来的空的区域即可。故只需对前一种情形进行证明。难点和关键在五构形。再给出定义“若正规地图所有的国家连成一片且内部没有空的区域，则称内部与外部的分界线（一条简单闭曲线）为正规地图的边界。”和定义“若国P的一段边界（不含一点）在正规地图的边界上，则称P为边沿国（便于分类）。”就可做出证明，有多处难点。思路如下：

⑴1≤n≤15时，易证明。

⑵假设15≤n≤k时，四色定理都成立；

以下是递推的分类及部分说明

按层次分为181种情形，涉及188个图。其结构可谓千奇万状，众多种情形的证法变化多端，国与国的合并个数与方式几乎无规律可寻，换色国从一国两国，到一批不知具体国家的情形多种多样。

前三种构形的情形极易证明。

对五构形

令Q有五个邻国。易知这五个邻国两两相邻的组数有0到7等八种情形。

当Q的五个邻国的关系是除两两相邻外两两没有公共点时

㈠相邻组数不大于四

把五个邻国两两相邻的组数从0到4的情形归为一类，其中有一种情形的证法很典型，具有“普遍”性。

㈡相邻组数是五

ⅰQ的邻国中不存在两国与Q形成圈

这时Q为非边沿国

①Q的五个邻国每一国的邻国个数都是五

若Q的五个邻国中没有边沿国

若Q的五个邻国中有边沿国

这时在Q的五个邻国的外部分别有五至十个国家与它们相邻，共135种情形。其中，沿一段边界，由一国与一国或一国与两国能把五构形分成两部分的有127种，不能分成两部分的有8种。

②Q的五个邻国每一国的邻国个数不都是五

此情形即是Q的五个邻国中至少有一国的邻国个数不小于六的情形，对此，要用到定理2。

ⅱQ的邻国中存在两国与Q形成圈

①有一个圈

②有两个圈

㈢相邻组数是六

ⅰQ为边沿国

ⅱQ为非边沿国

㈣相邻组数是七

ⅰQ为边沿国

ⅱQ为非边沿国

当Q的五个邻国的关系是除两两相邻外两两有公共点时

把上述各种情形中的边沿国Q在正规地图边界上的一段边界部分或全部地收缩成一点，即是此情形，相邻国家的组数和相邻关系没有改变，收缩为一点后形成众多种情形仍同之前所对应的情形的证明。

http://idea.cas.cn/docimages/sparkdoc/doc/201801/sparkdoc_doc_201801242125524355.JPG