[原创]我对Mycielski操作过程的研究与理解

雷明85639720

[watermark]

我对Mycielski操作过程的研究与理解
——四色猜测的又一证明方法
雷  明
（二○一三年十二月十二日）
1、Mycielski—操作过程
数学家狄拉克1953年在其论文《k—色图的构造》一文中提出一个问题：对于任意大的一个正整数k，是否存在一个图，不包含三角形但色数是k？这一问题分别在1954年和1955年分别由勃兰克•斯德卡兹和米歇尔斯基独立的作出了回答。米歇尔斯基（Mycielski）给出的由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法是：设Gk的顶点是u1, u2,……，un, 添加点v1,v2,……，vn和点v0。将vi与ui所有邻点及v0相连，1≤1≤n。如此得到的图就是一个不含三角形的k＋1色图。这里所说的三角形实际上就是基图Gk的密度是小于3的图。米歇尔斯基的这一构造方法在图论界把它叫做Mycielski—操作，且这一操作过程是可以递推的，即可以多次进行的。每进行一次Mycielski—操作，图的密度并不发生变化，但其色数却增加1。所以厦门大学的×××博士说：“Mycielski构造的图说明：存在无三角形且色数任意大的图”。实际上，进行Mycielski—操作时的基图的密度可以上任意的，不一定都得是密度小于3的图。
2、我对Mycielski—操作过程的理解
我对Mycielski—操作过程的理解是：色数为k的基图Gk的密度是ω（ω≥2），顶点数是u，添加顶点数是v＋1的v—星（v＝u，其密度是2）。再向后，上面的操作过程中的“将vi与ui所有邻点及v0相连，1≤i≤n”说得很不明确。根据Mycielski—图（如图1），我的理解是把顶点vi与基图中的两个不相邻的顶点ui，uj(1≤I，j≤n)相连，同样，也把ui与星形图中的两个不相邻的顶点vi，vj(1≤I，j≤n)相连，使得基图各顶点与星形图各顶点构成的圈的边数都大于3，保证了增加部分的图的密度不会大于2，这样就得到一个密度仍是ω（ω≥2，由于添加的星形图的密度已经是2，所以基图的密度也一定是要大于等于2 的），但色数却是k＋1的图Gk＋1。用一个图来表示则如图2。（图请见以上DOC文件）

由于星形图的各星点均不相邻，所以可以着同一颜色，星形图的中心顶点v0与基图Gk的各顶点全不相邻，所以把星形图的中心顶点着上基图中已用过的任何一种颜色即可。这时图的色数就成了k＋1。
为什么所添加的图要是一个星形图（密度是2）呢，是因为如果只添加一个顶点，这个顶点再与基图中各顶点均相邻时，必然该顶点就要与基图中k种颜色的每一种颜色的顶点都相邻，它只能着第k＋1种颜色。虽然色数比原来增加了1，但又因为这时该顶点也同时与基图中最大团的ω个顶点均相邻，图的密度也变成了ω＋1，图的密度也就比基图的密度ω也增加了1。若把添加一个顶点变成添加一个星点数与基图顶点数相同的星形图，则这时所有星点同着一种颜色，星形图中心顶点着基图中已用过的某一种颜色，图的色数虽变成了k＋1，但图的密度却没有增大，仍是ω。可见Mycielski的这一操作方法可真是费了心机。

3、平面图是不可进行Mycielski—操作的
由于Mycielski—操作过程可以多次使用，那么就可以得到任何密度下的图的色数都是没有上界的。可是，平面图（密度不大于4 的图）的四色猜测却说的是任意平面图的色数都不大于4，这却是有界的。这显然与上述结论不符，是有矛盾的。这能不能说四色猜测就不正确呢。还不能。还要看一看上述的Mycielski—操作过程对于平面图是否适用。如果Mycielski—操作过程对于平面图同样适用，则就证明了四色猜测是错误的。如果不适用，就有再进一步研究证明四色猜测的必要。
从Mycielski—操作过程中“把顶点vi与基图中的两个不相邻的顶点ui，uj(1≤I，j≤n)相连，同样，也把ui与星形图中的两个不相邻的顶点vi，vj(1≤I，j≤n)相连”可以看出，这一过程就出现了非平面图的特征——交叉边。比如，把v1与ui和uj相连后，再要把v2与ui和uj之间的某些顶点uk相连时，就必然出现v1—uj边与v2—uk边的交叉，等等等等。这一点在图1的Mycielski—图和图2中均可看到。可见平面图是不能进行Mycielski—操作的，那么平面图的色数就不可能是任意大的，而一定是有其上界的。
4、四色猜测的证明
既然平面图是不可进行Mycielski—操作的，那么某密度的平面图的色数就不是可任意大的。根据我们以前得出的在没有进行Mycielski—操作的情况下，任意密度的图的色数上界是其密度值ω与该图中可构成联的不可同化道路的条数S的和，就有平面图色数的上界是ω＋S。由于平面图的密度都不大于4，同时我们以前也多次证明了密度是1和4的平面图中是不存在饱和道路的，当然也就不存在不可同化道路了，其色数分别就是其密度的值1和4；也证明了只有在含有奇圈的密度是2的平面图和含有奇轮的密度是3的平面图中最多只可能有一条不可同化道路，即S＝1,并有其色数上界是ω＋1的结果。所以密度是2和3的平面图的色数最多也只可能是3和4。因为以上四种密度的平面图的色数都不大于4，这也就证明了四色猜测是正确的。

                         雷  明
二○一三年十二月十二日于长安

任道远

注意！
     一切应用数学都应该从纯粹数学谈起！
     因为纯粹数学是数学的理论基础！

雷明85639720

看图时请点击上面的DOC文件。雷明