地图“四色问题”中的特例——三色足够

焦永溢

             地图“四色问题”中的特例——三色足够

                     浙江奉化  焦永溢  2016.5.6

   关于地图四色问题，本人已写过多篇文章，于2007年5月21日发布在《少年百科》网站上的那篇《用减少法证明最大平面图“四色问题”》 已经用非常简便的方法能够完全证明最大平面地图（即球面平面地图）用四种颜色足够。后来于2009年6月27日在《少年百科》网站上重新发了一篇《简单明了的“四色问题”证明》，就是把前一篇文章加以整理，并增加了若干的插图，目的是为了使大家能够更加看得清楚明了。这些图中，图5展示了中心一个点、被周围共偶数个点包围的情况下，怎样去掉中心点，合并外围的点，然后用右边合并后的图在整个图中代替左边的图；而图6展示了中心一个点、被周围共奇数个点包围的情况下，怎样去掉中心点，合并外围的点，然后用右边合并后的图在整个图中代替左边的图。现在我再把这两个图拿来分析一下合并前后各个点度数（就是与该点相连的线条数）的变化。这里的图1和图2，分别用的是原来图5和图6下面的示意图，为了分析方便，把各个点作了编号。下面就去掉偶度数中心点和奇度数中心点这两种情况作如下分析；
    一、去掉偶度数的中心点（见图1）
    合并前，中心点是偶度数的，周围各点若不计对外相连的线数，图中从1-12各点都是三度（与左、右、中心各有一条连线）。合并后，中心点去掉了，外围的12并给了2，11并给了3，10并给了4，9并给了5，8并给了6。1和7点从合并前的三度（不计向外的连线，下同）减少到一度；而其它点都是两个合并后只剩二度。可见没与其它点合并的1和7点，在这合并处理后分别减少了二度；其它的二个点合并后的度数由原来的三度加三度减少到二度，减少了四度。
    二、去掉奇度数的中心点（见图2）
    合并前，中心点是奇度数的，周围各点若不计对外相连的线数，图中从1-11各点都是三度。合并后，中心点去掉了，外围的11并给了2，10并给了3，9并给了4，8并给了5，6和7相邻不能合并。与前一种情况相似，1点从合并前的三度减少到一度，其它两个点合并后只剩下二度，而合并后的5和8点却剩下三度，6和7点分别还剩下二度。可见1点在合并处理后减少了二度；5与8点合并后的度数由原来的三加三减少到三度，减少了三度；6和7点分别只减少了一度。
    大家知道，在整个最大平面图中，只要有三度及三度以上的奇度数点存在，就一定需要四种颜色（因为外围一圈就需要三种颜色了）。而偶度数的点，由于外围一圈只要二种颜色，包括中心点只要用三种颜色就够了；所以，只要保证图上所有的点在上述合并过程中一直都是偶度数的，不会有奇度数的点出现，就能保证三种颜色就够了。
    为了使全图上所有点一直都是偶度数的，首先合并前就一定都要是偶度数；那么在合并的过程中这些点能不能一直保证都是偶度数呢？上面第一种情况的分析中，1和7点都是减少了二度，所以减少后的度数（包括与外连线的度数）还是偶数（偶数减二当然还是偶数）；其它两个点合并后的度数，是两个点原来总度数（包括对外连线的度数）之和减少了四度，所以合并减少后的度数还是偶数（偶数加偶数减四当然还是偶数）。
    综上所述，我们在拿到任何复杂的地图时，只要看一下图中有否三度及三度以上的奇度数点存在，有就可断定这图可用四色着色；若全是偶度数点，没有奇度数点，就可断定这图用三色足够了。这一判断的方法，就如欧拉在“七桥问题”上得出的“看图上奇度数点的个数就能断定能否一笔画出”的结论一样的简单。

焦永溢

这个成果把“四色定理”进一步推向了“三色定理”。得出的结论是：图上有奇度数点，要用四种颜色；而图上没有奇度数点只有偶度数点，用三种颜色就足够了。

雷明85639720

说得对。这是判断一个平面图的色数的方法。但这一方法仍是在四色猜测是正确的前提下进行的，所以首先还是先要证明猜测是否正确。我认为还是不要再出现什么“三色定理”之类了，因为它全在四色猜测之内了。任何平面图的色数都不大于4，当然也就包括了色数是3的图了，即所在顶点都是3—度的平面图。。