四色定理的四色原理的一种逻辑证明
地图上任何一个区域必将存在邻域,且又通过邻域与其他非邻域发生间接联系,我们可以将任何一个地图以图论图形的表示出来。
假设存在一张至少需要m种着色的地图,那么决定该地图必须要用m种着色的条件有且只有一个,即该地图至少存在这样一个区域Q,与该区域相邻的所有区域必须满足m-1着色。首先满足这个条件后,Q只能用第m种颜色,其次如果这个推论一是错误的,对于m着色地图不存在这样的区域,那么地图上任何一个区域的邻域只能满足少于m-1的着色,那么整个地图势必不需要m中颜色,这与假设相矛盾,所以这是一个充分必要条件。(推论一)
假设随意取一张任意结构的至少m着色的地图M,其上满足上述条件的区域有n个,那么将图论图形中的这n个区域及其与邻域的关系线我们可以全部去掉,这样我们就将构建一个至少m着色地图M的问题转化成了一个在至少需要m-1着色地图上添加n个满足推论一条件的区域问题。
如果五着色地图存在且能构建成功,那么必然存在构建这样五着色的四着色模型图,而要存在这样的四着色模型图必然存在构建该四着色的三着色模型图,同理要存在这样的三着色模型图必然要存在构建它的二着色模型图,那么我们来构建一下五色图是否存在:
二着色地图是由一着色而来的一种简单的着色地图模型,我们很容易得到满足二着色的地图仅有的两种类型的结构,一种是不闭合的链状结构,如图一;另一种是由第一种衍生出来的闭合的环状结构且环所联系的区域为偶数个,称为偶数环,如图二。
我们看下二着色结构特点发现,图一图二都是一个原理就是奇偶位置决定着色,任何两个区域的任何联系链条只有相隔偶数个区域才满足两区域着色不同,我们定义这两个区域为偶隔域。
我们随意取一张任意结构的二着色的地图M,来构建一个具有n个满足推论一条件区域的地图Q,构建方式有且只有一个,就是在图论图形中我们如何去掉的这n个区域及其与邻域的关系线,我们接怎么给它添加回去。我们任取这n个区域中一个区域q为例,只要我们在M地图上将必须满足二着色的几个区域W直接联系到q上,这样就满足推论一中的条件而使Q必须为三着色。而W要满足二着色则必定含有偶隔域,如果W有x个区域和q发生直接联系,则q上出去的关系线有x个,那么我们一定可以将该复杂的联系分解成x-1个不可分解关系环,其中至少有一个不可再分的关系环是M中的偶隔域与q联系的,(推论二)假设这个推论是错误的,所有不可再分的环全部是奇隔域,那么这些环拼接回去时满足每个小环的间隔区域数相加再减去共用的区域,仍旧是奇隔域,这样W便不满足二着色,所以这些不可再分环中一定有偶隔域和q发生联系而构成奇数环(环连的区域为奇数),并且导致q必须使用第三色的就是这些不可再分的奇数环。由于满足二着色的只有偶隔域一种条件,那么构造的三着色地图中决定三着色的条件也只有一种,存在不可再分的奇数环。
在上面构建的三色着色地图Q基础上我们再来构建四着色地图P,假如P存在满足推论一条件的区域有k个,同样的方法,我们任取k中一个区域p,只要我们在Q地图上将必须满足三着色的几个区域R直接联系到p上,这样就满足推论一中的条件而使P必须为四着色。而R要满足三着色则必定含有奇数环并且组成奇数环的区域都能够与p发生联系(保证奇数环没有被包围在其他闭合环内的部分),如果R有y个区域和p发生直接联系,则p上出去的关系线有y个,那么导致p为第四色原因是可发生联系的奇数环,既只要有一个这样的奇数环存在就一定会导致p使用第四色(推论三),假设这一推论不成立那么没有这样的奇数环存在,则由前面二着色建立三着色正经得到,除了奇数环再没有能使地图为三着色的条件了,或者当奇数环区域不能全部与p发生联系,这样p必然的不需要第四色了。故我们的推论三成立。由于三着色条件唯一而使得p四着色的条件唯一,我们来看四着色条件的特点,当p与R发生联系后,不管R有多少满足条件的奇数环,势必最终只能有包括p在内的三个区域能与外界区域发生联系。因为p和R上的任何两个区域都可以构成一个封闭的三角形,而当我们选的R上这俩区域与p关系线是最外侧的关系线时,则R上其他区域一定不能在三角形外,不然或造成以上两根关系线不再是最外侧或者有关系线出现交叉,所以R上剩余区域必定在三角形内而造成四着色图最多只有三个区域能与外界发生联系。
那么我们在构建五着色地图时,四着色结构最多提供三种不同着色,不能满足推论一的条件,而决定将无法构建五着色地图。