一、四色定理

每幅㊣ (每一国连成一片,两国共同边界是条线而非有限的点,无一国包围其它国家,至多三国相遇一点)最多需要四种色能使相邻国着不同色.

它从1852年问世至今尚未获得数学证明.

符号含意:㊣正规地图,☆五构形,※PC被E分隔、PA相邻、CA不相邻,△根据归纳假设,□四色定理成立,⊙不妨视,P-1P着色1或着色是1.

二、定理 定义 引理

肯普定理:每幅㊣至少有一国有二、三、四或五个邻国,无每一国都大于五个邻国的情形.

按此㊣可分为二构形、…、☆四种情形.

定义：

1-对各种构形,称邻国数最少的国家为构形国.

2-约定㊣所有国家连成一片内部无空区域,并称内部和外部的界线（简单闭曲线）为㊣边界.

3-国B一段边界在㊣边界上,则称B为边沿国.

4-一些国家包围了其它国家,则称这些国家形成的环为圈.

引理1:☆的国家数的集W＝｛12,14,15,…,n,…｝.

证:构造无穷多“四圈”☆.类似图1的☆,内外圈各一国,中间两圈上取数列6,7,…,m,…（m≥6）⑴中的同一项,得国家数由大于12的偶数组成数列14,…,2（m+1）,…⑵；虚线将P分成两国,得国家数由大于13的奇数组成数列15,…,2m+3,…⑶. 易验证1-13中 仅12有☆.合并数列⑵⑶及12得到所有☆的国家数的集W=｛12,14,15,…,n,…｝.

除12外W中每个n所对应☆不同结构的个数复杂程度无论如何,皆视为由“四圈”☆演变而成.

引理2:任意☆中存在构形国不是边沿国.

证:假设命题不成立,则有一个☆G,使得构形国都是边沿国.因平面地图与球面地图等价,故可使G的以边沿国形成的圈T在球面上并把球面分成对称的两部分.令每部分被T包围的国家S对称地布满,示意如图2.由此知T上每一国的邻国数（原来不一定都是五）都大于七,其余国家的邻国数都大于五,就得到一幅（STS）每一国的邻国数都大于五的㊣.这与肯普定理矛盾,故G不存在.证毕.

引理3:在n≥15的☆中,若包围构形国Q的每个邻国与Q只有一条共同边界,Q的邻国两两相邻的组数是五,这五个邻国中存在邻国数大于五的国P,则□.

证:若☆每一国的邻国数都是五,则n=12.由类似图1的结构知n≥15时,每个n至少与一个“四圈”☆对应,故完全具备引理3的条件.

⑴n=15时,只有图3-5三种情形,图中国家数由内到外各依次为1563、1572及1662.图3,QP都具备引理3的条件.视AQ为E,B（P）由五（六）个邻国变成四（五）个,其余国家的邻国数未变,☆变成四构形；至多用四种色,使得四构形在不相邻的PC（※）着同色时相邻国家能着不同色,如P-1C-1E-3B-2D-2（1-2-3-4为色码,不会混淆）,其余国家着色如图,□；把Q换成色4,则□.图4,视AQ为E,BP都由六个邻国变成五个,其余国家的邻国数未变,还是☆；至多用四种色,使得☆在不相邻的PC（※）着同色时相邻国家能着不同色,如P-1C-1E-3B-2D-2,其余国家着色如图,□；把Q换成色4,则□（E的邻国数是六.图5类似可证）.

⑵假设15≤n≤k时□,图6,视PAQBCD依次着色是134212,即是说QP都具备引理3的条件,假设都是按上述模式操作的方法着色,视AQ为E,PEBCD依次着色是13212,显然BPE的邻国数分别不小于四五六,其余国家的邻国数未变,国家数满足14≤n≤k-1,除14外的每个n值,都含有A和Q合并前与后两种情况,前为☆后为四构形或☆.至多用四种色,使得每个n值所对应的四构形或☆在不相邻的PC（※）着同色时相邻国家能着不同色,⊙P-1C-1E-3B-2D-2（若BD异色,则与归纳假设相悖.如B-4,由n=k-1〔AQ合并后〕时□,但不能还原n=k时□）,即□（换色前）.把Q换成色4,□.

n=k+1时,图7,取一个具备引理3条件的构形国Q,视AQD为E,则 E的邻国数大于六,PBC的邻国数都不小于四.其余国家的邻国数未变,n=k-1（合并后）,其构形为四构形或☆.根据换色前的归纳假设,即…在不相邻的PC（※）着同色时相邻国家能着不同色,⊙P-1C-1E-3B-2,□（换色前）.把Q换成色4,□.证毕.

三、证明四色定理

证：1≤n≤15时已公认□.

假设15≤n≤k时□；

n=k+1时,令Q为构形国,分类论证如下.

㈠二构形

图8-11,视AQ为E,则n=k.△,□,⊙E-1B-2.把Q换成色3,□.

㈡三构形

1Q的每个邻国与Q 只有一条共同边界

图12,视AQ为E,则n=k.△,□,⊙E-1B-2C-3.因EBC只用了三种色着色,且Q被ABC包围,故Q能换成色4,□.

图13-15,视AQ为E,则n=k.△,□.因（Q是边沿国）BC至多用了两种色着色,故Q至少能换成第四色,□.

2Q的邻国中至少有一国与Q至少有两条共同边界

图16（不能有两个圈）-20,A与Q至少有两条共同边界.同图13的证明.

㈢四构形

1Q的每个邻国与Q只有一条共同边界

图21-26,视AQC为E（显然AC及BD中至少有一组不相邻,在图21-22中⊙AC不相邻）,则n=k-1.△,□.因EBD至多用了三种色着色（BD相邻为异色）,故Q至少能换成第四色,□.

2Q的邻国中至少有一国与Q至少有两条共同边界

这时若有Q的邻国AB分别与Q形成圈T和H,显然H在T内或外且互不干扰.即使有Q的两个邻国与Q形成圈S,S也在T内或外,故只需考虑一组T即可.当T或（可兼）S型圈超过一组时,均未也不必画出相应的图,如图19.☆也如此不再述.

T的个数是1,图27-34,因四构形每一国的邻国数都大于三,故T至少包围了两国（非下确界）.视T包围的国家为E,则n≤k,△,□,⊙A-1Q-2.因T外部至少有Q的一个邻国,去掉T外部的国家,则n≤k,△,□；因AQ只用了两种色,故总可使得A-1Q-2.把前次T及其外部的着色部分与后次T内部的着色部分拼成原来的四构形,□.图35,AC相邻时,A、Q与C形成两个圈,取一个圈仿图27的证明易证□；不相邻时,视AQC为E,同图22的证明（此法仅适于T及S型圈）.

T的个数大于1,图36-39,任取一个圈,按图27的证明（后次要去掉该圈外A的一部分）,再把所需的两部分拼成原来的四构形,□.

㈣五构形

由引理2可令Q不是边沿国.

1Q的每个邻国与Q只有一条共同边界

⑴Q的邻国中没有两国与Q形成圈

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

ⅰQ的邻国无边沿国,则Q的邻国被四国BCBDF或五国BCDFG形成的圈包围.图40,视BGHIJKQ为E,则n=k-5.△,□,⊙E-1D-2F-3C-2或4.把GHIJKQ重新着色成434312或232314,□.图41,视Q及邻国为E,则n=k-4.△,□,⊙圈上着色是12123,E-4.把E的六国重新着色,如图□.

ⅱQ的邻国有边沿国

Q的邻国有边沿国的位置只有一处

与某边沿处邻近的两国只有两种情形.图42, 若AB不是同一国,不相邻时,把AB拓展成相邻（不影响其它国家的相邻关系,下同此）并视为E,仿图8的证明易证□,再收缩成原状,□；相邻时,⊙C不是边沿国（在此处把AB拓展成相邻）,这时Q的邻国无边沿国,变为情形ⅰ已证.再收缩成原状,□.若AB是同一国, 则AC形成的圈T至少包围了五国.T外部至少有一国时,仿图27的证明易证□.T外部无国家时, 至少有一非Q的邻国R与AB相邻,示意如图44.否则☆只有7国,这与n＞15矛盾.把AB拓展成Q的邻国无边沿国而又在某处断开,使得无一国包围其它国家且R成为边沿国,就变成情形ⅰ,已证.再还原成原状, □.

图43, 若AB不是同一国,AB不相邻时,把A按箭头方向拓展成与B相邻并视为E,按图42“AB不相邻”的情形证明;AB相邻时,把A按箭头方向拓展成与B“相邻”,则C有六个邻国.此时同“②Q的邻国中每一国的邻国数不都是五”情形的证明. 再收缩成原状,□.若AB是同一国,拓展A使图43成为图42,按图42“AB是同一国”的情形证明.

Q的邻国有边沿国的位置至少有两处

图42-43,这时显然AB不是同一国也不相邻,仿图42“AB不是同一国,不相邻时”的情形易证明□.

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

此即Q的邻国中存在邻国数大于五的国家,对此引理3已证明n≥15时□.故此时□.

⑵Q的邻国中有两国与Q形成圈

图45,AQB形成一个（两种情形）或两个圈,取一个圈仿图27的证明易证□.

2Q的邻国中至少有一国与Q至少有两条共同边界

图46-51,AQ形成一个至三个圈,取一个圈仿图27或36的证明易证□.证毕.

参考文献:

R.柯朗（美国）著,《数学是什么》.