四色猜想的證明

呂振柱

【摘要】 四色猜想的證明已經(jīng)歷經(jīng)了一百多年，這個(gè)看似簡單的問題，卻難倒過大量的數(shù)學(xué)愛好者. 人們通過不斷努力，最終于1976年6月，由哈肯與阿佩爾合作編制一個(gè)很好的程序，在美國伊利諾斯大學(xué)的兩臺不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明. 但人們不滿足于計(jì)算機(jī)取得的成就，仍在尋找更簡單的證明方法. 我在證明四色猜想時(shí)，主要采用了轉(zhuǎn)化思想，把四色猜想的證明轉(zhuǎn)化成在平面內(nèi)是否存在五個(gè)圖形兩兩之間存在公共邊的證明，再轉(zhuǎn)化成在平面內(nèi)是否存在五個(gè)點(diǎn)兩兩相連，連線除了頂點(diǎn)之外沒有其他交點(diǎn)的證明. 這樣就大大簡化了四色猜想的證明，把復(fù)雜的圖論問題轉(zhuǎn)化成了簡單的連線問題，使人很容易理解、接受.

【關(guān)鍵詞】 四色猜想；兩兩相連；公共邊

地圖四色定理（Four color theorem）最先是由一位叫古德里（Francis Guthrie）的英國大學(xué)生提出來的. 四色問題的內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色. ”用數(shù)學(xué)語言表示，即“將平面任意地細(xì)分為不相重疊的區(qū)域，每一個(gè)區(qū)域總可以用1，2，3，4這四個(gè)數(shù)字之一來標(biāo)記，而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字. ”這里所指的相鄰區(qū)域，是指有一整段邊界是公共的. 如果兩個(gè)區(qū)域只相遇于一點(diǎn)或有限多點(diǎn)，就不叫相鄰的. 因?yàn)橛孟嗤念伾o它們著色不會(huì)引起混淆.

證明之前我們先看一下這個(gè)結(jié)論，“將平面任意地細(xì)分為不相重疊的區(qū)域，每一個(gè)區(qū)域總可以用1，2，3，4這四個(gè)數(shù)字之一來標(biāo)記，而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字”. 這個(gè)結(jié)論也就是說，在平面中存在四個(gè)或四個(gè)以下圖形兩兩之間有公共邊，而不存在四個(gè)以上的圖形兩兩之間存在公共邊，我們只需要證明平面內(nèi)不存在五個(gè)圖形兩兩之間有公共邊就可以了.

我們假設(shè)在平面內(nèi)存在五個(gè)圖形兩兩之間有公共邊，分別在這五個(gè)圖形內(nèi)各取一點(diǎn)，我們可以把這五個(gè)點(diǎn)命名為A，B，C，D，E，兩兩連接這五點(diǎn)，連線在被連接的兩個(gè)圖形內(nèi)，并且經(jīng)過它們的公共邊. 如果上述假設(shè)成立，我們必能作出這樣的十條線（AB，AC，AD，AE，BC，BD，BE，CD，CE，DE），并且這十條線除了頂點(diǎn)之外不會(huì)有其他的交點(diǎn).

我們通過作圖方法來證明上述結(jié)論，證明過程：

我們先任選兩點(diǎn)A，B，連接這兩點(diǎn)得到AB（AB可以是任意曲線，為了簡便，我們把它做成直線）.

再任取一點(diǎn)C，從C點(diǎn)向A，B做連線，得到AB，AC，BC這三條線，這三條線連接成了一個(gè)閉合的圖形（圖1），并把平面分成了兩部分.

然后我們再取一點(diǎn)D和A，B，C相連，D點(diǎn)可以在AB，AC，BC這三條線分割平面得到的兩部分中的任一部分（圖2，圖3），這樣的六條線AB，AC，AD，BC，BD，CD就把平面分割成了四部分，每部分都是由三個(gè)頂點(diǎn)、三條線分割開的.

我們再取第五點(diǎn)E，點(diǎn)E可以在由線AB，AC，AD，BC，BD，CD把平面分割成的四部分中的任何一部分內(nèi)，如果E點(diǎn)在線BC，CD，BD所分割的平面內(nèi)（圖4），那么點(diǎn)E只能和點(diǎn)B，C，D相連，如果要連接點(diǎn)A，必經(jīng)過BC，CD，BD這三條線中的一條，所以點(diǎn)E在這一部分不能和點(diǎn)A相連，以同樣的原理也可以推出當(dāng)點(diǎn)E在另外三部分的時(shí)候，只能和分割這一部分的三個(gè)點(diǎn)相連，不可以與第四個(gè)點(diǎn)相連. 因此我們可以得到，在平面內(nèi)，不存在這樣的五個(gè)點(diǎn)，兩兩相連后，連線除了頂點(diǎn)之外不相交.

從上面的這四個(gè)步驟中，我們一步一步推出了結(jié)論：在平面內(nèi)，不存在這樣的五個(gè)點(diǎn)，兩兩相連后，連線除了頂點(diǎn)之外不相交. 同時(shí)我們也就得到了在平面內(nèi)不存在五個(gè)圖形兩兩之間有公共邊，四色猜想也就得到了證明.