四色定理的簡(jiǎn)便證明

盧玉成

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

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

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

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

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

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

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

規(guī)定1：每?jī)蓚€(gè)有公共邊界的不同地區(qū)，有且只有一條公共邊界線，即不存在有三個(gè)或三個(gè)以上的不同地區(qū)共有一條邊界線（共用連接點(diǎn)除外），也就是說(shuō)，兩點(diǎn)之間用且只用一條線段來(lái)連接.

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

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

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

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

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

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

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

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

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

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

圖4

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

圖5

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

從上面的分析來(lái)看：一個(gè)點(diǎn)只使用一種顏色；一條線段有兩個(gè)端點(diǎn)，該端點(diǎn)需要使用兩種不同的顏色；一個(gè)三角形有三個(gè)頂點(diǎn)，該頂點(diǎn)需要使用三種不同的顏色.

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

圖6

圖7

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

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

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

圖8

圖9

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

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

圖10

圖11

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

圖12

圖13

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

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

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

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

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

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

圖14

圖15

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

由上述所知，5個(gè)不同的點(diǎn)兩兩彼此不能夠連接，這就是說(shuō)，在同一個(gè)平面上，盡管由原來(lái)不同的4個(gè)點(diǎn)增加到5個(gè)點(diǎn)，多了一個(gè)點(diǎn)，但顏色的種數(shù)并沒(méi)有增加，這是因?yàn)橛幸粚?duì)點(diǎn)不能連接，該兩點(diǎn)所表示的不同地區(qū)可以取同一種顏色，即存在有1對(duì)點(diǎn)著色相同，此時(shí)，仍然需要使用a，b，c，d四種不同的顏色就可以區(qū)別開(kāi)來(lái).

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

在如圖15所示的基礎(chǔ)上，再增加一個(gè)點(diǎn)F，共計(jì)6個(gè)點(diǎn).

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

圖16

圖17

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

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

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

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

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

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

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

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