《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（五）

雷明85639720

（接上贴）

三十多年研究四色问题的总结：《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（五）

不用“不可免集”证明四色猜测的四种方法
雷  明
（二○一七年元月三十一日）

    1、用哈德维格尔猜想来证明
哈德维格尔猜想已经被证明是正确的，我们完全就可以利用这个猜想或者叫做定理来证明四色猜测了。
哈德维格尔猜想说：任何色数是n的图，一定可以同化（同化即收缩运算，就是把图中不相邻的顶点凝结在一起的过程）为一个完全图KN。因为四色问题研究的对象是平面图，所以我们首先要假设图是一个亏格是0的、色数是n的平面图。根据哈德维格尔猜想，这个图一定是能同化为一个完全图 Kn的，这个完全图Kn的亏格也一定是0，是一个平面图，否则就与假设发生了矛盾。
已知平面图中最大的完全图是K4，即在平面图中，所有完全图的顶点数n都是小于等于4的。所以也就有原图的色数n也是小于等于4的。而原图我们已经假设它是亏格为0的平面图了，所以这就证明了任何平面图的色数都是小于等于4的。四色猜测是正确的。
证毕。
2、用图的色数一定等于图的最小完全同态的顶点数来证明
哈拉里在他的《图论》一书中说：任意图的色数一定等于它的最小完全同态的顶点数。所谓完全同态就是利用同化运算把图变成一个顶点数最少的完全图，这个完全图就是原图的最小完全同态。显然，同化时一定是把不相邻的顶点凝结在一起的，而不相邻的顶点也是可以着成同一颜色的。当然最后的最小完全同态的顶点数就一定是原图的色数了。
同样也是因为四色问题研究的对象是平面图，所以我们首先要假设图是一个亏格是0的平面图。当然其最小完全同态的亏格也一定是0，是一个平面图，否则也就与假设发生了矛盾。
平面图中完全图的顶点数一定是小于等于4的，所以平面图的最小完全同态的顶点数也一定是小于等于4的，根据哈拉里说的任意图的色数一定等于它的最小完全同态的顶点数的理论，也就证明了任何平面图的色数都是小于等于4的。四色猜测是正确的。
证毕。
3、用不可同化道路的条数小于等于图的密度的一半来证明
①　不可同化道路是图的某个最大团外的一条道路。该道路中总有一个顶点同化不到最大团中去（图见前面的《用增加图的色数证明四色猜测的两种方法》（简称《两种方法》）一文中的图1。下同）。如一个5—圈，最大团是K2，5—圈中每个K2团外的其他顶点中，总有一个顶点是不能同化到这个K2团中去的（图见《两种方法》一文中的图2等）。若有S条这样的道路构成了联时，就应有S个顶点同化不到最大团中去。这是因为联中的每一条路中的每一个顶点都与其他道路中的所有顶点均相邻的原因。但这S条道路的联的密度（即联中最大团的顶点数，它是构成联的各条道路的密度2之和）2S一定是小于等于图的密度（图中最大团的顶点数）ω的，即有2S≤ω，所以有S≤ω/2。
②　由于图的色数一定是不会小于图的最大团的顶点数的，所以图的色数γ的下限是ω≤γ，同化不到最大团中去的顶点的颜色，必须用最大团各顶点所用颜色以外的颜色，所以图的色数的上限是γ≤ω＋S≤ω＋ω/2≤1.5ω。因此就有图的色数的界是ω≤γ≤1.5ω。
③　因为四色问题研究的对象是平面图，而平面图的密度一定是小于等于4的，即平面图中最大团的顶点数一定是小于等于4的。把平面图的密度ω＝1，ω＝2，ω＝3分别代入图的色数的界ω≤γ≤1.5ω中，都有γ≤4的结果，不可同化道路的条数S最大也都是1，且都小于等于2和3的一半；而把ω＝4代入ω≤γ≤1.5ω中时，就出现有γ＞4的可能，但我们可以证明在密度ω＝4的平面图中，根本就不可能存在不可同化道路，即S＝0。
④　密度ω＝4的平面图中，根本就不可能存在不可同化道路的证明：
这里首先要把不可同化道路与最大团的关系再说明一下：设最大团的顶点数是ω，不可同化道路的顶点数是n，这n个顶点均与最大团中的ω－2个顶点相邻，不可同化道路的两个端点顶点又分别与最大团中的另外两个顶点之一相邻。这样的道路中一定有一个顶点是同化不到最大团中去的。
在最大团与不可同化道路构成的系统中，顶点数是ω＋n个，其边数总数是：①　最大团的边数ω（ω－1）/2，②　不可同化道路的边数n－1，③　二者相邻的边数n（ω－2）＋2三者之和。即系统的总边数是ω（ω－1）/2＋n－1＋n（ω－2）＋2。当ω＝4，上式就成为6＋3n＋1＝7＋3n，而顶点数是4＋n的平面图的最大顶点数是3×（4＋n）一6＝12＋3n－6＝6＋3n，显然7＋3n＞6＋3n。这时的图就不再是平面图了。所以，密度是ω＝4的平面图中，就不可能有不可同化道路的存在。其色数也就不可能大于最大团的顶点数4。
综上所述，各密度条件下的平面图的色数都不大于4，这就证明了四色猜测是正确的。
4、用米歇尔斯基操作来证明
米歇尔斯基操作（简称M—操作）是一个作图的方法。是作一个图的色数比原图的色数大1的方法。该方法是：在顶点数是n的原图外，作一个n—星，使星的中心顶点u0不与原图的任何顶点相邻，星点顶点ui只与其所对应的原图中的vi顶点的相邻顶点相邻（ui与vi并不直接相邻），这样得到的图的色数就会比原图的色数大1，但图中的最大团的顶点数却并不增大。如一个K2图的色数是2，进行了M—操作后得到一个5—圈，这个5—圈的色数是3，比原图K2图的色数大1，但其最大团仍是K2，最大团的顶点数仍是2（图见《两种方法》一文中的图6）。
①　从以上M—操作的定义可以看出，密度是2的平面图的色数最大也只能是3，只能比其最大团的顶点数（密度）大1。因为对顶点数大于等于4的圈进行M—操作后，图就不再是平面图而是非平面图了（图见《两种方法》一文中的图10，其证明在本文的后面）。所以说密度是2的平面图的色数是不会大于3的。
②　一个K3图（3—圈）的色数是3，进行了M—操作后得到一个既有3—圈，又有4—圈的平面图，色数是4，比原图大1（图见《两种方法》一文中的图9）。同样，也因为对顶点数大于等于4的圈进行M—操作后，图就不再是平面图而是非平面图了。所以说密度是3的平面图的色数是不会大于4的。
③　一个K4图（3—轮）的色数是4，进行了M—操作后得到的是一个非平面图（读者可以自已画图试试），所以说密度是4的平面图的色数是恒等于4的。
④　至于K1图（平凡图），其色数是1，在进行了M—操作后得到的图的色数虽然是2，但得到的图却是一个密度是2的、不连通的平面图（图见《两种方法》一文的图5），图的最大团发生了变化，所以说密度是1的平面图也是不能进行M—操作的。
综上所述，在各种条件下的平面图，进行了M—操作后，所得到的图仍是平面图时，其色数都是不大于4的，这也就证明了四色猜测是正确的。
⑤　顶点数大于等于4的圈，在M—操作后所得的图不再是平面图的证明：
n—圈的顶点数是n，边数也是n；n—星的顶点数是n＋1，边数是n；n—圈上的每个顶点都与两个顶点相邻，所以n—星的每一个星点顶点都与原图中的2个顶点相邻，共有2n条边。这样一个n—圈的M—操作系统图中：顶点数是n＋n＋1＝2n＋1个，边数是n＋n＋2n＝4n条。2n＋1个顶点的平面图的最大边数只可能是3（2n＋1）－6＝6n＋3－6＝6n－3条。当n＝4时，图的边数则是4×4＝16，虽然不大于该图是平面图时的最大边数6n－3＝6×4－3＝21，但图中已明显的产生了不能去掉的交叉边，是一个非平面图了（图见《两种方法》一文中的图10）。这就证明了顶点数大于等于4的圈，在M—操作后所得的图就不再是平面图了。
边数大于3v－6的图一定不是平面图，但边数小于等于3v－6的图却不一定都是平面图，比如K3，3图，有6个顶点，9条边，小于3v－6＝3×6－6＝12，但K3，3却是一个典型的非平面图。
⑥　K4团在M—操后所得的图不再是平面图的证明：
K4团的顶点数是4，边数是6；4—星的顶点数是5，边数是4；M—操作所增加的边数是4×3＝12（一个星点与K4团中的三个顶点相邻）。系统总顶点数是9，边数是22。22大于9个顶点时的平面图的最大边数3v－6＝3×9－6＝21，显然就不再是平面图了。这就证明了K4团在进行了M—操后所得的图就不再是平面图了。

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

注：此文已于二○一七年二月一日在《中国博士网》上发表过，网址是：

证明四色猜测的其他三种方法
雷  明
（二○一七年元月三十一日）

1、用反证法进行证明
五色地图就是需要用五种颜色着色的地图，最小五色地图就是地图中只有五个区域，且每两个区域都是相邻的地图。按坎泊的想法，如果不存在五色地图时，则地图四色猜测就是正确的。
现在我们假设这种五色地图存在，则一定也存在最小的五色地图。由于最小五色地图中每一个区域都与其他的四个区域相邻，所以每个区域就有四条边界线，五个区域共有二十条边界线，但每条边界都是两个区域所共有，所以该最小五色地图实际只有十条边界线（即图的边数e＝10）。又由于地图是一个3—正则图，所以有3v（v是顶点数）＝2e（e是边数）的关系。把最小五色地图的边数e＝10代入3v＝2e中，得到顶点数v＝20/3，不是整数，这是不符合实际情况的，应该否定假设。说明我们假设的最小五色地图是不存在的。
按坎泊的想法，这也就证明了地图四色猜测是正确的。同样的，平面图的四色猜测也是正确的。四色猜测正确。
2、用数学归纳法进行证明
用v表示图的顶点数，e表示图的边数，f是图的面数，γ表示图的色数。
当v＝1时，一种颜色就够用了，γ＝1＜4；
当v＝2时，两种颜色也就够用了，γ＝2＜4；
当v＝3时，边数最多时是K3图，是一个极大图，也是一个完全图，两两顶点均相邻，必须用三种颜色着色，γ＝3＜4；
当v＝4时，新增加的这第4个顶点，只有位于上面的K3图的一个面内时，最多可以增加3条边，使K3成为一个极大图K4，也是一个完全图，两两顶点也均相邻，着色时四种颜色也就够用了，γ＝4≯4；

当v＝5时，新增加的顶点，可以在图中的一个面内，也可以在图的一条边上，只要在图不变成非平面图的情况下，尽可能多的使该顶点与图中的其他顶点都相邻，最后都可以成为一个极大图：若该顶点处在图的一个面内时，它只能与三个顶点相邻（如图1，a），还有除了三个顶点所着颜色以外的第四种颜色可着；若该顶点是处在图中的一条边上时，它也只能与四个顶点相邻（如图1，b和图1，c），按照坎泊1879的证明，这个顶点一定是能着上四种颜色之一的。这就证明了v＝5时的极大图也是可4—着色的，其色数γ＝4≯4。
从图1中还可以看出，不管增加的顶点是增加在何处，图中都是因增加了1个顶点而增加了3条边和两个面。若再在图中增加顶点，仍是增加一个顶点最多增加3条边和两个面时，图都不会变成非平面图，且所得到的图一定都是极大图，就一定都是可4—着色的，色数都是γ＝4≯4；
当v＝k时，这个极大图当然也是可4—着色的，色数仍是γ＝4≯4。已知在极大图中都有e＝3v－6和f＝2v－4的关系，所以这里也应有e＝3k－6和f＝2k－4的关系；当v＝k＋1时，按上面的证明和分折，所增加的这一个顶点不但是可以着上图中已用过的四种颜色之一的，而且图中也因增加了这一个顶点而增加了三条边和两个面，使得图的边数和面数分别变成了e＋3和f＋2。代入上两式得：e＋3＝3（k＋1）－6和f＋2＝2（k＋1）－4，化简后仍有e＝3k－6和f＝2k－4的关系，所以图仍是一个极大的平面图。
到此就证明了任何极大图都是可4—着色的。因为在相同顶点数的平面图中，极大图的边数是最多的，所以边数比极大图少的任意平面图的色数也一定是不会大于4的。这也就证明了四色猜测是正确的。
3、用断链法进行证明
一个构形的待着色顶点，如果其围栏顶点占用的颜色数未达到4时，该待着色顶点都是可以直接着上四种颜色之一的；如果围栏顶点已占用完了四种颜色，则必须想办法从围栏顶点中空出一种颜色来，然后给待着色顶点着上。如何空出颜色，这就得灵活的运用坎泊的颜色交换技术了。
用坎泊的颜色交换技术，空出颜色来给待着色顶点着上的原则是：首先要看，在以待着色顶点为中心顶点的轮中，对角顶点间的颜色所构成的色链是不是连通链，如果是不连通的链时，才可以进行交换，也才能空出颜色给待着色顶点。而如果是连通链时，即就是交换了这种链也是空不出颜色来的。
4—轮构形中只可能有一条连通链，另一条则一定是不连通的。该构形一定是可以通过坎泊的颜色交换，空出一种颜色给待着色顶点着上的。而5—轮构形的情形就不同了，其中有可能有两条连通链的情况。若两链只有一个共同的起点（或是只有一个交叉顶点）时，也一定是可以通过坎泊的颜色交换，空出颜色来给待着色顶点的。而只有当两条连通链既有共同的起点，中途又有交叉顶点时，则难以通过交换5—轮对角链的办法解决问题。这种情况怎么办？可以想到，既然不连通的链是可以交换的，那么是否可以把已连通的链变成不连通的呢？完全可以。没有了连通链，或者只有一条连通链，一定是可以通过交换空出颜色给待着色顶点的。这种方法我们叫做“断链法”。
断链方法的原理是：用四种颜色A、B、C、D所能构成的链有六种，即A—B、A—C，A—D，B—C，B—D和C—D六种。如果在5—轮轮沿顶点（即围栏顶点）外有A—C链是连通的时，则该链中的A色和C色的顶点在该链以外，只能与B色和D色的顶点相邻，构成A—B链和A—D链或者C—B链和C—D链。从A—C链上的任何一个A色或C色的顶点起，开始交换上述的A—B链或A—D链（或者C—B链或C—D链）中的一种，都可以使A—C链上开始交换的A色顶点或C色顶点变成B色或D色，使A—C链断开。这一步就是“断链的交换”，只能断链，但不能空出颜色，只能为下一步空出颜色的交换，作好技术上的条件准备。 A—C链已经断开了，成了不连通的链，这样就可以对5—轮轮沿中的A色顶点或C色顶点施行A—C链的空出颜色的交换，空出A或C来给待着色的5—轮中心顶点着上。
我们在对赫渥特图和敢峰—米勒图的着色中，使用的就是这种方法。可以说任何平面图中的任何链都是可以通过这一方法“断开”的。连通链断开了，就可以通过施行坎泊的空出颜色的交换技术，空出已用过的四种颜色之一，给待着色顶点着上。所以也就可以说，任何平面图着色时是不会用到第五种颜色的。这也就证明了四色猜测是正确的。

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

注：此文已于二○一七年二月一日在《中国博士网》上发表过，网址是：

多阶曲面上图的欧拉公式是如何得来的
雷  明
（二○一七年五月二十二日）

多面体和平面图的欧拉公式，在文献和教课书中，有各种各样的证明方法，对于多阶曲面上图的欧拉公式，在沙特朗的《图论导引》一书中也有用数学归纳法进行的证明。这给人们一个印象是，欧拉公式好象是一个从经验中总接出来的公式，与四色猜想一样，也必须通过证明才能确定其是否正确，才可以进行应用。实际上这些证明同用着色的方法对平面图的不可免构形的所谓“证明”一样，都是在对命题进行验证而已，其根本的原理还是不能真正被揭开的。真正的证明应是进行数学上的严密推导后，从而得出的命题。平面上或多阶曲面上图的欧拉公式也是可以经过严密的数学推导而得到的。
1、亏格为0的平面图的欧拉公式的推导：
亏格为0的、不同顶点数v（v≥3）的平面图中的边数e和面数f有如下表一的关系：
                                               （表一）
序号        顶点数        v        3        4        5        6        v≥3
1        边  数        e        3        6        9        12        e＝3v－6
2        面  数        f        2        4        6        8        f＝2v－4

    根据表一，画顶点分别是3、4、5、6的极大平面图如图1。其中图1，a和图1，b又是完全图。从表一中可以看出，顶点数从3开始，每增加一个顶点，图的边数增加3条，面数增加2个。边数与面数分别和顶点数的关系是e＝3v－6和f＝2v－4。
用e＝3v－6减去f＝2v－4得：
e－f＝v－2
变形整理得
        v＋f＝e＋2                                     （1）
公式（1）就是平面图的欧拉公式。用同样的办法，也可以推导出其他亏格条件下图的欧拉公式。

2、亏格为1的非平面图的欧拉公式的推导：
亏格为1的、不同顶点数v（v≥5）的非平面图中的边数e和面数f有如下表二的关系：
                                                                （表二）
序号        顶点数        v        5        6        7        8        v≥5
1        边  数        e        15        18        21        24        e＝3v
2        面  数        f        10        12        14        16        f＝2v

2、1  根据表二，画环面（轮胎面）上的顶点数是5的极大图的展开图如图2。图2，a是K5（K5是完全图而非极大图）图的展开表示方法，有10条边，5个面；但图中有一个面，是由顶点2—3—5—2—4—5—3—4—2构成的八边形面（如图2，b），所以K5图不是极大图；这个八边形面还可以分成6个三边形面，增加了5条边（也如图2，b），所增加的边分别是顶点2到5，顶点2到4，顶点2到3，顶点5到4和顶点3到4这五条边的各一条平行边（如图2，c）。这样就使图中的边数增加到15条，面数增加到10个，使图变成了一个极大图。


2、2  再根据表二，画环面（轮胎面）上的顶点数是6的极大图的展开图如图3。图3，a是K6（K6也是完全图而非极大图）图的展开表示方法，有15条边，10个面；但图中有一个面，是由顶点2—3—6—4—3—5—2构成的六边形面（如图3，b），所以K6图不是极大图；这个六边形面还可以分成4个三边形面，增加了3条边（也如图3，b），所增加的边分别是顶点2到3，顶点2到6和顶点3到6这三条边的各一条平行边（如图3，c）。这样就使图中的边数增加到18条，面数增加到12个，使图也变成了一个极大图。
2、3  图4是根据表二，画在环面（轮胎面）上的顶点数是7的极大图的展形图。其中a和b分别是两个K7（K7图既是完全图又是极大图，边数最多是7×6÷2＝21，图中没有平行边）图的不同展开表示方法，有21条边，14个面；再在图中增加顶点时，每增加一个顶点，也只能增加三条边和两个面，才能保证图的亏格不变。

2、4  根据以上（表二）和图2、图3和图4可以看出，亏格为1的极大图中每增加一个顶点，增加三条边和两个面，图的边数与面数和顶点的关系分别是e＝3v和f＝2v，两式相减得：
    e－f＝v即v＋f＝e                              （2）
（2）式与（1）式有明显的差别，需要变形把它们统一起来。
3、亏格为0和1的图的欧拉公式：
把亏格为1的非平面图的e＝3v和f＝2v与亏格为0的平面图的e＝3v－6和f＝2v－4都进行变形，并把图的亏格参数n代入其中，使e＝3v－6和f＝2v－4分别变成e＝3v－6（1－n）和f＝2v－4（1－n），当n＝0时, 等于给等式e＝3v－6和 f＝2v－4右边的常数项各乘了一个1，其值不变；使e＝3v和f＝2v也分别变形成e＝3v－6（1－n）和f＝2v－4（1－n），当n＝1时,等于给等式e＝3v和f＝2v的右边各减了一个0，其值仍不变。但这一变化，却使得两种不同亏格的图的边数与面数和顶点数的关系式统一了起来，是有好处的。再用e＝3v－6（1－n）减去f＝2v－4（1－n），得到：
    e－f＝v－2（1－n）
变形整理得
        v＋f－e＝2（1－n）                             （3）
公式（3）就是亏格为0 和1的图的欧拉公式。代入（表一）和（表二）中的数据验证如下：
①　当n＝0和v＝6时，e＝3v－6（1－n）＝3×6－6×（1－0）＝18－6×1＝12，f＝2v－4（1－n）＝2×6－4×（1－0）＝12－4＝8，均与（表一）中的数据相同；
再把n＝0，v＝6，e＝12和f＝8代入欧拉公式v＋f－e＝2（1－n）中得到，公式左边＝v＋f－e＝6＋8－12＝2，公式右边＝2（1－n）＝2×（1－0）＝2，左右相等，公式成立；
    ②　当n＝1和v＝8时，e＝3v－6（1－n）＝3×8－6×（1－1）＝24－6×0＝24，f＝2v－4（1－n）＝2×8－4×（1－1）＝16－4×0＝16，也均与（表二）中的数据相同；
再把n＝1，v＝8，e＝24和f＝16代入欧拉公式v＋f－e＝2（1－n）中得到，公式左边＝v＋f－e＝8＋16－24＝0，公式右边＝2（1－n）＝2×（1－1）＝2×0＝0，左右相等，公式成立；
    4、多阶曲面上图的欧拉公式：
我们现在还不会画出更高级亏格的图的展开图，虽然很难看清楚顶点与边和面间的关系，但却因为亏格n≥2时，一个亏格下只有一种完全图，我们可以利用亏格为0和1的图的顶点与边和面间的关系求得该完全图在极大图状态下的总边数和总面数。我们还知道在极大图中，以后图中每增加一个顶点时，仍是增加三条边和两个面。这样，我们就可以用上面得到的亏格是0和1时图的欧拉公式对其进行检验，看该公式是否也适用于亏格更高级的图。
4、1  亏格为n＝2，v＝8的极大图，最大顶点数是e＝3v－6（1－n）＝3×8－6×（1－2）＝24＋6＝30，最大面数f＝2v－4（1－n）＝2×8－4（1－2）＝16＋4＝20；因为以后再增加顶点时，每增加一个顶点，都是增加三条边和两个面，当然v＝9时，e＝33和f＝22；
把n＝2，v＝9，e＝33和f＝22代入上面得到的欧拉公式v＋f－e＝2（1－n）中得，公式左边＝v＋f－e＝9＋22－33＝－2，公式右边＝2（1－n）＝2×（1－2）＝2×（－1）＝－2，公式两边相等，公式对于亏格n＝2的图也是成立的。
4、2  亏格为n＝3，v＝9的极大图，最大顶点数是e＝3v－6（1－n）＝3×9－6×（1－3）＝27＋12＝39，最大面数f＝2v－4（1－n）＝2×9－4（1－3）＝18＋8＝26；同样以后再增加顶点时，每增加一个顶点，都是增加三条边和两个面，当然v＝10时，e＝42和f＝28；
把n＝3，v＝10，e＝42和f＝28代入上面得到的欧拉公式v＋f－e＝2（1－n）中得，公式左边＝v＋f－e＝10＋28－42＝－4，公式右边＝2（1－n）＝2×（1－3）＝2×（－2）＝－4，公式两边相等，公式对于亏格n＝3的图也是成立的。
4、3  继续再进行检验时，无论亏格是多大的图，上面由亏格为0和1的图所得到的欧拉公式也是适用于任意亏格的图的。所以说公式（3）v＋f－e＝2（1－n）也就是多阶曲面上的图的欧拉公式。同时，上面得到的图的边数与面数和顶点间的关系，e＝3v－6（1－n）和f＝2v－4（1－n），也就一定适用于任意亏格的曲面上的图了。这样通过严密的数学推导，所得到的欧拉公式是不需要再进行证明的。因为严密的数学推导过程就是证明的过程。
4、4  从以上的研究可以看出，同亏格曲面上的同顶点数的图，以完全图的边数e＝v（v－1）/ 2为界，边数小于e＝v（v－1）/ 2者是非完全图，边数等于e＝v（v－1）/ 2者是完全图，这两者均是单纯图；而边数大于于e＝v（v－1）/ 2者是则是多重图，因为图中有平行边。当边数等于e＝3v－6（1－n）时，图就成了极大图，所有的面均是三边形面了。所以在同亏格的曲面上，相同顶点数的图中，按边数的多少排序时，图的顺序是：非完全图的边数≤完全图的边数≤极大图的边数。因为有些图既是完全图，又是极大图，如K3，K4，K7等，所以又有：单纯图的边数≤多重图的边数。同样，图的面间也有相应的关系。在相同亏格、相同顶点数的图中，不管图是完全图还是多重图，顶点着色数都是相同的，因为平行边和环是不影响图的顶点着色数的。

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

注：此文已于二○一七年五月二十三日在《中国博士网》上发表过，网址是：

（未完，接下贴）

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

,,,,,,,,