四色定理的数学证明

四色定理 每一幅正规地图至多需四种色，能使相邻国着不同色。

正规地图的边界和边沿国的定义、构型分类、颜色数码等见参考文献。符号含意 △-根据归纳假设，□-四色定理（也）成立。

证：当1≤n≤15时，公认已验证□（略）。

假设15≤n≤k时，□；

当n=k+1时，按正规地图分类

㈠二、三及四构形按所给图易证（略。四构形要用德.摩根定理：没有五国处于每一国都和其余四国相邻的位置）

㈡五构形

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

1 Q的五个邻国的关系是除两两相邻外两两无公共点

⑴相邻组数不大于四

这时Q为边沿国，如图14－23，图21表两种情形。不妨把前10种情形对应的图中着色是1的三国与Q视为国E，则n=k－2。△，□，Q的其余两邻国至多用了两色，不妨着色是2和3。故Q至少能换成色4，这时□（图18只能如此相邻，因本证明证的参考文献附录中前一种情形—正规地图内部无空区域）。

如图23，Q的两邻国A、B与Q形成圈T并包围了别的国家。因五构形每一国的邻国个数都不小于五，故T至少包围了两国（非下确界。以下有类似表述），其中有一国与Q相邻。把被T包围的国家视为一国，则n≤k。△，□，不妨A-1、B-2、Q-3。因T外部至少有Q的两个邻国，去掉T外部的国家，则n≤k－1。△，□；因A、B与Q用了三种色，故总能使A-1、B-2、Q-3。把前次T及外部着色部分与后次T内部着色部分拼成原来的五构形，这时□。

⑵相邻组数是五

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

这时Q为非边沿国。

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

若Q的五个邻国中无边沿国，则Q的五个邻国被BCDFG形成的圈包围（图37是反向包围），如图24。把被包围的六国视为E，则n=k－4。△，□，不妨视圈上着色是12123，E-4。把被包围的六国重新着色，易使相邻国着不同色，这时□。

若Q的五个邻国中有边沿国，在Q的五个邻国外部分别有五至十国与它们相邻，见附图B。其中，沿一段边界由一国与一国（或两国）能把五构形分成两部分的有127种，以序号8为例（其余可类似证明，略）。

序号8，如图25，外部有六国与Q的五个邻国相邻，当由一国与一国能分成两部分时，把A与B视为M，则n=k。△，□，不妨M-1。因A向外的分支只有A与B相邻（否则内部有空的区域），故可把此分支中着色是2或3或4的与着色是1的互换（含A），则□。当由一国与两国能分成两部分时，仍以此为例，把C与D视为F，则n=k。△，□，不妨F-1，E-2。因C向外的分支只有C与D、E相邻，故可把此分支中着色是3或4的与着色是1的互换（含C），则□。

序号6，如图26，把着色是1的两国与Q及邻国DFGHK视为E，则n=k－6。△，□，不妨A-2，B-3。若C-4（3或2），把DFGHK的着色依次换成色24323（24324或24343），则□。

序号7，如图27，把着色是1的一国与Q及其邻国DFGHK视为E，则n=k－5。△，□，不妨A-2，B-3。若M-4，N-4（4、3或2、3或2、4），把DFGHK及Q依次重新着色成432321（414312或414312或413412），则□。

序号22、25与66的分别如图28、29与32，把A与B视为E，则n=k。△，□，不妨E-1，C-2。因A和C向外的分支只有A、C与B相邻、C与D相邻，故可把此分支中着色是3或4的与着色是1的互换（含A），则□。

序号26，如图30，把A、B、Q视为E，则n=k－1。△，□，不妨E-1、D-2、G-3。若N-2或3，把Q换成色4，则□。若N-4，因FMC向外的分支只与ANB相邻，故不妨C-2，则M-3，F-2或4。把此分支中着色是2的与着色是4的互换（含C与F。若无着色是4的，只把C换成色4），则N可换成色2，Q就换成色4。则□。

序号27，如图31，不妨把着色是1的与H及Q、是2的与D及K、是3的与F及G分别视为E、P、N，则n=k－5。△，□。由此ABC的着色依次分别是311、312、314、341、342、344、411、412、414、441、442、444，就可把DFGHK及Q的着色各依次重新着色成424213、424213、421413、124243、124243、121243、424213、421213、421213、312314、321214、321214，则□。

序号67，如图33，把A、B视为E，则n=k。△，□，不妨E-1、C-2，D-3、F-1或4。因ACF向外的分支只与BD相邻，可把此分支中着色是1的与着色是4的互换（含A与F。若无着色是4的，只把A换成色4），则□。

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

此即Q的五个邻国中至少有一国的邻国个数不小于六的情形，Q的五个邻国中不存在是否有边沿国的限制，由参考文献中定理2知，当然n=k＋1时□。

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

因在相邻的组数是五时存在两国与Q形成圈，则Q必为边沿国。

ⅰ有一个圈

把图34中着色是1的三国与Q视为国E，则n=k－2。△，□。因Q的其它两邻国相邻用了两色，不妨着色是2和3。故Q能换成色4，这时□。

如图35，同或仿图23中情形的证明（略）。

如图36，记M、N与Q形成的圈为T。若T外有国家，则至少有一国与M或N相邻，但不与Q相邻。这时同或仿图29中情形易证明（略）。若T外无国家，先把M与N在Q的边沿处拓展为相邻（M与N相邻的特殊情形）再在原相邻处收缩为不相邻，这不影响其它国家的相邻关系，就转化为M与N和其它三国形成的圈包围了Q，如图37。这时同情形①ⅰ中Q的五个邻国无边沿国或①ⅱ中的证明（略）。故按原操作的逆序逐步还原（两种情形），这时□。

ⅱ有两个圈

如图38，取A、B与Q形成的圈，同图23中情形的证明（略）。

⑶相邻组数是六

①Q为边沿国

Q的邻国中存在两国与Q形成两个圈。如图35、39至42。这时都可取A、B与Q形成的圈，证明同图23中情形的证明（略）。

②Q为非边沿国

Q的邻国中存在两国与Q形成一个或两个圈。

如图43至47，取A、B与Q形成的圈，同或仿图23中情形的证明（略，图45至47是特殊情形）。

如图48，当A、B与Q形成左右两个圈S和T时，它们至少各包围了11国，这时A与B形成一个圈H且至少包围了23国（含Q）。若H外部无国家，则把被S包围的国家视为一国，则n≤k－9。△，□，不妨A-1、B-2、Q-3。同样，把被T包围的国家视为一国，则n≤k－9。△，□；因A、B与Q用了三种色着色，故总能使A-1、B-2、Q-3。把前次S及外部着色部分与后次T外部着色部分拼成原来的五构形（S-123，T-123），这时□。若H外部有国家，则把被H包围的国家视为一国，则n≤k－21。△，□，不妨A-1、B-2。因H外部有国家，去掉H外部的国家（至少有一国），则n≤k。△，□；因A、B用了两种色着色，故总能使A-1、B-2。把前次H及外部着色部分与后次H内部着色部分拼成原来的五构形，这时□。

⑷相邻组数是七

①Q为边沿国

如图49至51，在各自形成的三个圈中，不妨取A、B与Q形成的圈T，同图23中情形的证明（略）。

②Q为非边沿国

如图52，A、B与Q，A、C与Q分别形成圈T、H，T与H在Q的同（异）侧，不妨取T，证明仿（同）图23中情形的证明（略）。此外，如图48，A、B与Q及A、C与Q不可能都形成两个圈（比如当前者形成两个圈后，后者C就受到前者B所拓展区域的限制，后者形成第二个圈的路径被B阻断），最多能形成三个圈，即将图48中的“线段”a移到虚线b的位置或B收缩（C拓展）到使C和B的一段边界都在a上，其证明同图48中当A、B与Q形成左右两个圈S和T情形的证明。

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

把上述各种情形中（含㈠）的边沿国Q在正规地图边界上的那段边界部分或全部收缩成一点，相邻国家的组数和相邻关系都不会改变，就得到改变后的此情形。因正规地图无三个以上的国家交于一点，故收缩为一点后此边沿处的区域仍无国家。如此形成的众多情形，同之前所对应情形的证明（略）。证毕。

参考文献

陈陶，《关于四色定理的两个定理》，北京，《科学智慧火花》

？科学智慧火花》

http://idea.cas.cn/docimages/sparkdoc/doc/201802/sparkdoc_doc_201802031931580011.JPG

http://idea.cas.cn/docimages/sparkdoc/doc/201802/sparkdoc_doc_201802031932084100.JPG