与梁增勇朋友交换意见

雷明85639720

与梁增勇朋友交换意见
雷  明
（二○一八的年四月二十二日）

增勇朋友：
四色问题说的是对任何一个图（且是一个具体的平同图或地图）着色时，四种颜色就够用了。在证明时，应该是先给出一个具体的图，然后再进行着色，并使其只剩一个顶点未着色，而其他顶点均已着上四种颜色之一，并符合着色要求——相邻顶点或区域不着同一颜色。这就是所谓的构形。然后再想办法对图中的那个未着颜色的待着色顶点进行着色。当与这个未着色顶点相邻的顶点已占用完了四种颜色时，就得使用坎泊创造的颜色交换持术。未着色的顶点可能是处在一个轮的中心顶点位置，也可能不是；与未着色相邻的顶点可能占用完了四种颜色，也可能没有占完；与未着色顶点相邻的顶点的个数可能是小于等于3的，也可能是大于3的（包括大于5）。由于任何平面图中一定存在度小于等于5的顶点，所以在证明时只研究未着色顶点的度是小于等于5就够用了，因为我们总可以把未着色顶点放在度是小于等于5的顶点上。这也就可以把一个无穷的问题变成有穷的问题。
但增勇朋友的着色法中，却不是对一个已知的具体图进行着色，而是一步一步增加新的顶点，一步一步去对所增加的新顶点进行着色，这样，图是一直处在一个变动之中的，而不是一个具体的图，而不符合先给出一个具体的图，然后再去着色的条件。增勇朋友所增加的新顶点，若在图的内部各面中时，这个顶点的度只能是3（因为增勇朋友的图的内部面全是三角形面），这个顶点一定可以着上第四种颜色；当增加的新顶点处在图中的无限面中时，该顶点就不可能处在一个轮的中心顶点上。其度虽是任意的，但总可以使与其所相邻的顶点所点用的颜色少于4，该顶点着第四种颜色也就可以了；即就是与该顶点所相邻的顶点已占用完了四种颜色，但由于该顶点处在一个非轮中心顶点上，比处在一个轮中心顶点上的着色要容易解决得多。

比如图1，可调整的颜色是2、3、4。当在1、3间不存在1、3链（即增勇朋友的迹）时，可以把3改成1，给新增V着上3即可：但在1、3间有1、3链时，3和1就都不能进行调整，这时在2和4间一定不存在2、4链，把2改4或把4改2，都可以空出一种颜色来给新增V着上。
    而当图中只剩下一个顶点V未着色时（如图2），增勇朋友能否用你的“双迹法”给其着上图中已用过的四种颜色之一呢。
雷  明
二○一八年四月二十二日于长安

zengyong

你的问题问得很好。

先答复例图1的问题如下图2，将图1中的色为4的顶点改为2，然后新顶点v用颜色4就行了。

因为改色2的顶点可能会与旧的1-2迹的顶点产生颜色冲突，将冲突的1-2迹的顶点调换颜色变成2-1迹
（也就是将1色顶点与2色顶点调换颜色），那么冲突就会消除。如图4.

雷明85639720

1、“将图1中的色为4的顶点改为2，然后新顶点v用颜色4就行了。”要说明为什么要这样做。因为光你知道还不行，一定要让大家都知道为什么要这么做。
2、你这一步后，实际上并没有产生颜色冲突，不要图4也是可以的。
3、在图4中本来红色1的顶点就是着的色，改后仍是1色，也就更没有必要画图4了。
4、请你按你的方法把我的五个图着色完成，就可以证明你的方法是否能证明四色猜测是否正确，因为我的那五个图是我经过证明是完备的H—构形的不可免集中的构形。

zengyong

1、        问：“将图1中的色为4的顶点改为2，然后新顶点v用颜色4就行了。”要说明为什么要这样做。因为光你知道还不行，一定要让大家都知道为什么要这么做。“
答：这不是明摆着的吗？在图1中，新顶点和1、2、3、4四种颜色的 顶点相邻接。必须将这四个顶点的颜色改变，才能让新顶点有可用的颜色。同时右上角形成一个1、2、3、4的合理分布。
按照这样的道理，选色为2的顶点改为也行，但你的图没画完不是三角形结构图，不好分析。
为什么不选两边色为1的顶点下手？因为，外围的 顶点最好不改动，以免影响更大面积的顶点要改动。再说两边色为1的顶点外面的顶点是什么颜色也 不 清楚。总的 原则，能在你提供的子图中改变颜色是最直观和影响最小的。

2、        问：你这一步后，实际上并没有产生颜色冲突，还要图4也是可以的。
答：因为你的 图没画完。如果2是被3-4迹的顶点“拦“住，使它不与后面的1-2迹的顶点相冲突（或者1-2迹的顶点刚好是1色顶点与它邻接），那么整个步骤就是像图2一样就OK了。但是我要从多种可能最差的情况着想，即2色顶点又遇到后面的2色顶点（即颜色冲突）该如何处理？这样才有图3和图4的假设和处理方法。
既然好的和差的情况都能解决。那么你提出图1的问题就解决了。

4、问：请你按你的方法把我的五个图着色完成，就可以证明你的方法是否能证明四色猜测是否正确，因为我的那五个图是我经过证明是完备的H—构形的不可免集中的构形。
答：可以的，但画图和打字需要时间，慢慢来，别着急。

zengyong

图2的处理方法如下：图发重复了，不知道如何删去。以后面的为准。

雷明85639720

增勇朋友，高兴的看到了你的着色。
1、我上贴中说：“比如图1，可调整的颜色是2、3、4。当在1、3间不存在1、3链（即增勇朋友的迹）时，可以把3改成1，给新增V着上3即可：但在1、3间有1、3链时，3和1就都不能进行调整，这时在2和4间一定不存在2、4链，把2改4或把4改2，都可以空出一种颜色来给新增V着上。”这就是我对图1的着色法。你对图1的着色也是对的。我的图已画出，没有必要考虑更多的图未画部分的可能了。当然你能考虑这些，也是可以的。但你只考虑了最下边一行中间的顶点是2的情况，如果在这一行中最右边一个顶点又是2的情况时，你该 怎么办呢。所以说，图已经给出，你就按图着色就可以了，不必考虑得更多。我不是说了吗，“在1、3间有1、3链时”，就是说，在上边一行的着色为1和3的顶点间有1、3迹存在，所以你的改动也就没有必要了。只所以你要改动的原因可能是我的“在1、3间有1、3链时”说得不太明白的关系，1、3道底是顶点名，还是颜色序号，别人难以理解。
2、你所给图2的着色，可能不对，你看看吧。你把5—轮中着3色的顶点，改成了2色，把3色给V着上，但你可能没有看到最外面的3—圈中还有最下边一个顶点是着2色的，与你改着过的2色顶点是相邻的，都用2色是不合适的。
3、我的图2中，有一条环形的3、4迹（坎泊把你这里的的“迹”叫做“链”），有两条互不连通的1、2迹（其中一条1、2迹中只有一个顶点着2）。我已看出来了，你的第一步“把一个3色改为2色”后，按你画的图，两条迹都成了单条。这里我想请教一下，你是不是对每个图着色时，都必须把图中的相反的两种迹都得变成单条呢。如果是这样，你得要说出理由为什么要这样做才是。

zengyong

由于赶时间，图4 的颜色标号是错误的，两个2碰在一起。现将图4重作。

我的作图方法是：先画好迹，不管迹的标号如何。迹是否画对的标准是一条迹不能形成奇
圈。最后才把每条迹的标号注明。这在以后的五图着色方案更体现出来。

当你领会了双迹法，你会觉得很容易的。因为它不像以前的作图方法，要每一个顶点的左右上下都考虑到。（注意：我指的是每一个，并不等于都不考虑）。

zengyong

“3、我的图2中，有一条环形的3、4迹（坎泊把你这里的的“迹”叫做“链”），有两条互不连通的1、2迹（其中一条1、2迹中只有一个顶点着2）。我已看出来了，你的第一步“把一个3色改为2色”后，按你画的图，两条迹都成了单条。这里我想请教一下，你是不是对每个图着色时，都必须把图中的相反的两种迹都得变成单条呢。如果是这样，你得要说出理由为什么要这样做才是。”

不是的，因为在这么小的图空间只能画做两条了。看下图：用3-4迹把1-2迹分成两个小迹。结果3-4迹成了奇圈，没法正常着色了。

如果图大，还是分成几个迹好。如果强求也是两条单迹是很困难的。（有点要求作哈密顿图的意思。）

zengyong

像下面的图G和图G'是同一个原图的两个着色方案。都是可以达到正常4-着色的。图G有3个红迹和两个蓝迹；图G'仅有两个单迹。

为了省事，我都画成直线了，同时没有顶点标号。

zengyong

雷明朋友，应你的要求已将你的五个图完成正常4-着色。