盧玉成

在每一張地圖上，不論行政區(qū)域多么復雜，最多使用四種顏色，就能夠給所有有公共邊界的不同地區(qū)著有不同的顏色加以區(qū)別開來，這就是著名的四色定理.下面，我們給出四色定理的一種簡便證法.

一、沒有公共邊界的不同地區(qū)

沒有公共邊界的不同地區(qū)，只需要使用同一種顏色就可以區(qū)別開來.例如，山東省與黑龍江省沒有公共邊界，這兩個省可以使用同一種顏色；再如，海南省、臺灣省以及海域中的諸島等也可以使用同一種顏色.

二、含有公共邊界的不同地區(qū)

含有公共邊界的不同地區(qū)，著有顏色的種數(shù)多少與不同地區(qū)兩兩彼此有公共邊界的多少有關(guān)，兩兩彼此有公共邊界的不同地區(qū)越多，著有顏色的種數(shù)就越多.

兩兩彼此有公共邊界的含義是指每兩個地區(qū)都含有公共邊界.例如，甲、乙、丙三個不同的地區(qū)兩兩彼此有公共邊界，就是說，甲地與乙地有公共邊界，甲地與丙地有公共邊界，乙地與丙地有公共邊界；甲、乙、丙、丁四個不同的地區(qū)兩兩彼此有公共邊界，就是說，甲地與乙地有公共邊界，甲地與丙地有公共邊界，甲地與丁地有公共邊界，乙地與丙地有公共邊界，乙地與丁地有公共邊界，丙地與丁地有公共邊界.

地圖上的不同地區(qū)，我們可以分別用點A，B，C，D，E…來表示；不同地區(qū)所著用的不同的顏色分別用a，b，c，d…來表示；相鄰不同地區(qū)的公共邊界，用連接兩點（表示該相鄰的地區(qū)）之間的一條線段來表示，并且每條線段的兩個端點所表示不同的地區(qū)所使用的顏色是不同的，這樣，不同地區(qū)的著色問題可以看做是不同點的著色問題.

規(guī)定1：每兩個有公共邊界的不同地區(qū)，有且只有一條公共邊界線，即不存在有三個或三個以上的不同地區(qū)共有一條邊界線（共用連接點除外），也就是說，兩點之間用且只用一條線段來連接.

規(guī)定2：連接的所有線段除端點外，既不能重合，也不能相交.

這樣我們將上述四色問題可以轉(zhuǎn)化為：

在同一個平面上有m個不同的點，從中任取一個點Pi（i=1，2，…，m）與其余（m-1）個點連接，并且連接任意兩點之間的線段除端點外，既不能重合，也不能相交，則在這m個不同的點中，能夠兩兩彼此相連接的點最多有4個.下面我們給出證明.

證明：一個點或多個孤立（互不相連接）的點均可以使用同一種顏色；一條線段有兩個端點，這兩個端點表示不同的兩個地區(qū)，該線段表示有公共邊界，這樣的兩個地區(qū)，只需要兩種不同的顏色即可區(qū)別開來.

現(xiàn)在，我們來研究由線段組成的圖形.

1庇蒼（n為正整數(shù)）條線段組成的一條或多條沒有封閉的圖形

我們知道，每一個端點（或拐點）表示不同的地區(qū)，兩個相鄰的不同地區(qū)的公共邊界用一條線段來表示，由n（n為正整數(shù)）條線段組成的一條或多條沒有封閉的圖形，其所有端點（所表示的不同地區(qū)），可以需要使用a和b兩種不同的顏色即可區(qū)別開來.如圖1和圖2所示.

需要特別指出的是在同一條線段（或直線）上的點，如圖3所示，當A，B，C三點在同一條線段上時，線段AC與線段AB，BC重合，這意味著它們有兩條公共邊界線，這與“不同地區(qū)有且只有一條公共邊界線”矛盾，因此，我們說“連接AB，BC”，此時不能說“連接AC”.不能說“連接AC”的意思是說地區(qū)A和C沒有公共邊界，它們可以取同一種顏色.

2.由n（n≥3）條線段組成的一條封閉的圖形

（1）當n為奇數(shù)時，該圖形中的所有頂點（所表示的不同地區(qū)），可以需要使用a，b，c三種不同的顏色即可區(qū)別開來，如圖4所示.

圖4

（2）當n為偶數(shù)時，該圖形中的所有頂點（所表示的不同地區(qū)），可以需要使用a，b兩種不同的顏色即可區(qū)別開來，如圖5所示.

圖5

三、在三角形的基礎(chǔ)上，增加一個點所構(gòu)成的圖形

從上面的分析來看：一個點只使用一種顏色；一條線段有兩個端點，該端點需要使用兩種不同的顏色；一個三角形有三個頂點，該頂點需要使用三種不同的顏色.

設(shè)存在有三個不同的地區(qū)兩兩彼此有公共邊界，即存在不共線的三個點A，B，C連接成一個三角形，如圖6所示，在這個平面上增加一個點D，有如下情況：

圖6

圖7

由于不同的點表示不同的地區(qū)，所以點D與三角形的頂點不能重合，即點D不能在三角形的頂點處；當點D在△ABC的任一條邊上時，不妨假設(shè)點D在邊AC上，如圖7所示，由于線段AC與線段AD，CD重合，這與規(guī)定“所有線段不能重合”矛盾，所以點D不能在△ABC的任一條邊上.

顯然，如果有4個不同的點，其中有三個點A，B，D兩兩彼此相連接（即A，B，D三點所表示的地區(qū)兩兩彼此有公共邊界），也就是說點B與A連接、點B與D連接、點D與A連接；第4個點C與點B連接，與點D連接，而點C與A不連接（此時，點A，C所表示的兩個不同地區(qū)沒有公共邊界線），且A，D，C三點共線，此時，點A與C可以取同一種顏色（我們可以看做點C在△ABD的外部如圖7所示），那么這樣的4個點所表示的不同地區(qū)，可以使用a，b，c三種不同的顏色就可以區(qū)別開來.這樣，我們只研究點在三角形的內(nèi)部和外部兩種情況就可以了.

1.當點D在△ABC內(nèi)部時，如果第4個點D與三角形的三個頂點A，B，C兩兩彼此相連接，如圖8所示，那么所有頂點所表示的不同地區(qū)，需要使用a，b，c，d四種不同的顏色就可以區(qū)別開來.

圖8

圖9

2.當點D在△ABC外部時，（1）不妨假設(shè)點D在線段AC所在的直線上，即點D，A，C三點共線，如果能夠連接DB，DA，那么所有頂點或端點所表示的不同地區(qū)，需要使用a，b，c三種不同的顏色就可以區(qū)別開來，如圖9所示.

（2）不妨假設(shè)點D不在線段AC所在的直線上，且點D與B在線段AC所在直線的兩側(cè)，如果能夠連接DA，DB，DC，且線段DB與線段AC不相交，那么所有頂點（或端點）所表示的不同地區(qū)，需要使用a，b，c，d四種不同的顏色即可區(qū)別開來，如圖10所示；若能夠連接DA，DC，當連接DB時，線段DB與線段AC有可能“相交”，則所有頂點（或端點）所表示的不同地區(qū)，需要使用a，b，c三種不同的顏色即可區(qū)別開來，如圖11所示.

圖10

圖11

（3）不妨假設(shè)點D不在線段AC所在的直線上，且點D與B在線段AC所在直線的同側(cè)，如圖12和圖13所示，此時，結(jié)果與②類似，不必贅述.

圖12

圖13

由上述所知，如果每4個點滿足兩兩彼此相連接，且連接的所有線段除端點外，既不能重合，也不能相交，那么這樣的4個點所表示的不同地區(qū)，只需要使用a，b，c，d四種不同的顏色即可區(qū)別開來.

四、在如圖8所示的基礎(chǔ)上，增加一個點所構(gòu)成的圖形

我們從上面的分析可以得到一般結(jié)論：在同一個平面上，存在3個點，如果滿足兩兩彼此相連接，且連接的所有線段除端點外，既不能重合，也不能相交，那么這樣的3個點所表示的不同地區(qū)，需要使用三種不同的顏色；在同一個平面上，存在4個點，如果滿足兩兩彼此相連接，且連接的所有線段除端點外，既不能重合，也不能相交，那么這樣的4個點所表示的不同地區(qū)，需要使用四種不同的顏色.

我們自然要問：在同一個平面上，存在5個點或5個以上的點，如果滿足兩兩彼此相連接，且連接的所有線段除端點外，既不能重合，也不能相交，那么這樣的5個點或5個以上的點所表示的不同地區(qū)，就需要使用五種或更多種不同的顏色嗎？回答是不可能的.這是因為，在同一個平面上，有5個點或5個以上的不同點是不可能存在兩兩彼此相連接，且連接的所有線段除端點外，既不能重合，也不能相交的，從而說明，在同一個平面上，不存在超過四種不同的顏色.我們給出如下推理：

在如圖8所示的基礎(chǔ)上，再增加一個點E，共計5個點，有如下幾種情況：

（1）如果第5個點E落在△ABC的外部，那么點E與△ABC內(nèi)部的點D不能夠連接.假設(shè)點E與D能夠連接，由于△ABC是一個封閉的圖形，一個點E在△ABC的外部，一個點D在△ABC的內(nèi)部，當連接ED時，必然與△ABC中的某一條邊相交，這與規(guī)定（所有的線段不相交）矛盾，所以說盡管點E能夠與點A，B，C兩兩彼此相連接，但點E與點D不能夠連接，因此，5個不同的點兩兩彼此不能夠相連接.此時，點E和點D可以使用同一種顏色著色，這樣的5個不同點所表示的不同地區(qū)，可以需要使用a，b，c，d四種不同的顏色就可以區(qū)別開來，如圖14所示.

圖14

圖15

（2）如果第5個點E落在△ABC的內(nèi)部，那么點E必然會落在△ABC內(nèi)部中△ABD，△BCD和△ACD三個三角形中的某一個三角形的內(nèi)部.不妨假設(shè)點E落在△ABD的內(nèi)部，如圖15所示，此時，點C在△ABD的外部，由（1）知點E與C不能夠連接，因此，5個不同的點兩兩彼此不能夠連接.此時，點E與C可以使用同一種顏色著色，這樣的5個不同的點所表示的不同地區(qū)，可以需要使用a，b，c，d四種不同的顏色就可以區(qū)別開來.

由上述所知，5個不同的點兩兩彼此不能夠連接，這就是說，在同一個平面上，盡管由原來不同的4個點增加到5個點，多了一個點，但顏色的種數(shù)并沒有增加，這是因為有一對點不能連接，該兩點所表示的不同地區(qū)可以取同一種顏色，即存在有1對點著色相同，此時，仍然需要使用a，b，c，d四種不同的顏色就可以區(qū)別開來.

五、在如圖15所示的基礎(chǔ)上，增加一個點所構(gòu)成的圖形

在如圖15所示的基礎(chǔ)上，再增加一個點F，共計6個點.

1.如果第6個點F在△ABC的外部，那么點F與△ABC內(nèi)部的點E或D不能夠連接，也就是說，6個不同的點兩兩彼此不能夠連接，如圖16所示.新增加的點F的著色可以取與點D的顏色相同（新增加一對著色點），點E的著色可以取與點C的顏色相同（原有的一對著色點），這樣共有2對相同的著色點，這說明顏色的種數(shù)并沒有增加，仍然需要使用a，b，c，d四種不同的顏色就可以區(qū)別開來.

圖16

圖17

2.如果第6個點F在△ABC的內(nèi)部，那么點F必然會落在△ABE，△BED，△AED，△BCD，△ACD這5個三角形中的某一個三角形的內(nèi)部.不妨假設(shè)點F落在△BDC的內(nèi)部，如圖17所示.顯然，新增加的點F與A不能夠連接，它們可以取相同的顏色（新增加一對著色點）；點E與C不能夠連接，它們可以取相同的顏色（原有的一對著色點），這樣存在2對相同的著色點，因此，6個不同的點兩兩彼此不能夠連接.也就是說，盡管由5個不同的點增加到6個不同的點，又多了一個點，但顏色的種數(shù)并沒有增加，這是因為有2對點著色相同，此時，仍然需要使用a，b，c，d四種不同的顏色就可以區(qū)別開來.

類似地，第k（5≤k≤m）個點落在如圖8所示的圖形中，（1）如果第k個點落在△ABC的外部，那么第k個點與△ABC的內(nèi)部的某一點不能夠連接，因此，有k個點兩兩彼此不能夠連接，同時可以看出，第k個點可以取與△ABC的內(nèi)部的某一對應點（不能連接）的著色的顏色相同，這樣顏色的種數(shù)沒有增加，第k個點的情形與第（k-1）個點的情形的著色相同；（2）如果第k個點落在△ABC的內(nèi)部，那么必然會落在且只能落在△ABC被分割成（2k-5）個不重疊三角形中的某一個三角形的內(nèi)部，此時，該點與該三角形的外部的點不能夠連接，且有（k-4）對點（不能連接的）著有對應相同的顏色，這說明顏色的種數(shù)并沒有增加.

綜上所述，在同一個平面上，超過4個不同的點，兩兩彼此不能夠連接，這就是說能夠兩兩彼此連接的點最多有4個，所以，在一張地圖上的所有有公共邊界的不同地區(qū)，最多使用四種不同的顏色就可以加以區(qū)別開來，四色定理成立.證畢.

我們根據(jù)上述判定方法來詮釋中國政區(qū)地圖，為何最多使用四種不同的顏色.

在《中華人民共和國地圖》（人民交通出版社，2003年8月第3版）上，因為最多有4個不同地區(qū)兩兩彼此有公共邊界，這4個省兩兩彼此有公共邊界的地區(qū)分別是寧夏回族自治區(qū)、內(nèi)蒙古自治區(qū)、甘肅省和陜西省，即甘肅省與內(nèi)蒙古自治區(qū)有公共邊界，甘肅省與陜西省有公共邊界，甘肅省與寧夏回族自治區(qū)有公共邊界；內(nèi)蒙古自治區(qū)與陜西省有公共邊界，內(nèi)蒙古自治區(qū)與寧夏回族自治區(qū)有公共邊界；陜西省與寧夏回族自治區(qū)有公共邊界.換句話說，如果把這4個不同地區(qū)分別看成A，B，C，D四個不同的點，由于它們兩兩彼此有公共邊界，也就是說這4個不同點能夠兩兩彼此相連接.如圖8所示，甘肅省相當于點B，內(nèi)蒙古自治區(qū)相當于點A，陜西省相當于點C，該三點A，B，C能連接成一個三角形，寧夏回族自治區(qū)相當于△ABC的內(nèi)部的一個點D，根據(jù)上面得到的結(jié)論，可以判斷這張《中華人民共和國地圖》的著色，最多使用a，b，c，d四種不同的顏色就可以繪制而成.見附件一：《中國政區(qū)四色地圖》著色分布圖.

再如，在《世界地圖》（人民交通出版社，2003年8月第3版）上，我們看到有公共邊界的國家，最多有巴拉圭、巴西、玻利維亞及阿根廷這4個國家兩兩彼此有公共邊界（還有坦桑尼亞、莫桑比克、贊比亞和馬拉維4個國家兩兩彼此有公共邊界），它們分別用4個不同的點來表示，則這4個點之間兩兩彼此相連接，根據(jù)上面得到的結(jié)論，可以判斷這張《世界地圖》也需要使用a，b，c，d四種不同的顏色，就能夠保證相鄰國家著有不同的顏色加以區(qū)別開來（圖形略）.

附件一：方案不唯一，僅供參考.

我們?nèi)绻胊，b，c，d分別表示四種不同的顏色，那么不同地區(qū)的著色可以分別記成：著有a色的地區(qū)有新疆、陜西、安徽、湖南、云南以及海洋；著有b色的地區(qū)有黑龍江、遼寧、山東、山西、浙江、廣東、貴州、甘肅、西藏；著有c色的地區(qū)有寧夏、吉林、河北、福建、江蘇、湖北、四川、廣西；著有d色的地區(qū)有內(nèi)蒙古、青海、重慶、河南、江西；沒有公共邊界的海南和臺灣及其海洋中的諸島均可取同一種顏色（可以取不同于a色繪制），如選d色；上海市可以取d色；北京市可以取a色；天津市可以取d色；香港或澳門可以取d或c色.