[原创]图论法证明四色猜测（摘要）.

雷明85639720

[watermark]

图论法证明四色猜测（摘要）
雷  明
（二○一○年三月十六日）
    本文采用不对任何图着色的方法，只研究图的结构，推导出了任意图的色数与图的密度的关系，即任意图色数的界，再把平面图的密度不大于4的特点代入这个界中，就得到了任何平面图着色的色数总不大于4的结论。证明了四色猜测 是正确的。
1、图的色数、顶独立集、完全同态的关系
任何图中互不相的顶点可以着以相同的颜色；互不相邻的顶点也可以划归在同一个顶独立集内；互不相邻的顶点也可以同化为一个顶点。这样，任何图的色数γ就等于图的最少顶独立集的个数β，也等于图的最小完全同态的顶点数α，应有γ＝β＝α的关系。现在的关键问题是要求出图的最小完全同态的顶点数α与图的最基本参数——密度ω的关系。
2、最大团外的团向最大团的同化
任何图中最大团Kω的顶点数ω就是图的密度，最大团外的任何团Km（m≤ω）的各个顶点与最大团中所相邻的顶点数只能是小于等于ω－1个，否则，图的密度就要比ω大了。这些属于最大团中的顶点的并集一定是一个顶点数小于等于ω－m个的属于最大团中的Kn（n≤ω－m）团，那么，最大团Kω中至少还应有ω－m个顶点可以让团Km中的各个顶点同化到最大团中来。
3、单条道路向最大团的同化
一条道路Pn是由若干个K2团相互邻接而成的，应该说道路中的每个顶点也都可以同化到最大团中去，但是当道路中各顶点都与最大团中相同的ω－2个顶点相邻，且道路的两个端点顶点同时又还与最大团中另外的两个顶点（K2团）之一相邻时，在这种情况下，道路中各顶点只可能向最大团中的同一个属于最大团中的K2团中的两个顶点进行同化，这样问题就简化成了一条道路向一个K2团同化的问题了（如图1，图中只画出了部分关键顶点和边）。这时，又可以首先把道路本身同化成一个K2团（道路本身的最小完全同态就是K2团），这时，问题就又变成为一个K2团向另一个K2团同化的问题了（如图2）。

图1中的两图由于道路的奇偶性的不同，道路自身同化后分别就成为图2的四个图了。图1的a图中当n为奇数时，就成为图2的a图了，总有一个顶点同化不到最大团中去；图1的b图中当n为偶数时，就成为图2的d图了，也总有一个顶点同化不到最大团中去。这时，图同化的最后结果——最小完全同态的顶点数α就要比图的密度ω大1了。当然如果不把道路Pn本身进行同化，直接把Pn中各顶点向最大团中的那个K2团进行同化时，也会得到同样的结果。如果道路Pn是一个回路（即圈），也有同样的结果。我们把总有一个顶点同化不到最大团中去的道路称为不可同化道路。

4、多条道路向最大团的同化
如果有以上的道路S条，但各条道路之间没有形成联，各条道路同化不到最大团中去的那S个顶点因其本身就不相邻还可再同化为一个顶点（因为S条道路间没有联，所以同化时总可以把各条道路互不相邻的顶点作为不可同化的顶点），其实际仍与只有一条这种不可同化道路的情况一样，只有一个顶点同化不到最大团中去。
如果S条道路间有联存在，则各条道路同化不到最大团中去的那S个顶点因其本身就是相邻的而不可能再同化成一个顶点，所以就有S 个顶点同化不到最大团中去。这样，图的最小完全同态的顶点数α就应是α＝ω＋S，其色数也就是γ＝ω＋S。现在的问题是要确定S与图的密度的关系。
5、任意图着色色数的界
S条有Pn道路的联中，可能的最大团只能是2S（每一条道路提供两个顶点即时个K2团，S条道路就有2S个顶点的团），而且其一定是小于等于图的密度的，即有2S≤ω或S≤ω/ 2。由于道路的条数必须是整数，所以S还得向下取整，即S≤ 。这时就有图的色数的上界是：γ＝ω＋S≤ ＋ ≤ ，由于图的色数至少是大于等于图的密度的，即γ≥ω，把上两式合写在一起就得到任意图着色色数的界：ω≤γ≤ 。
6、四色猜测的证明

已知平面图的密度是不大于4的，这就有可能使我们把仅有的四种密度值代入到任意图着色色数的界中，结果得到任何平面图的色数都是小于等于4的。初看起来在ω＝4时，其色数有可能大于4，但在这种情况下的图已不再是平面图了（如图3，a图的色数是5，b图的色数是4，但两图都不是平面图，因为图中出现了交叉边。）。由此可以得出任何平面图着色时，其色数一定不会大于4，即γ平≤4。这就证明了平面图的四色猜测是正确的。
地图本身就是平面图，而平面图的对偶图仍是平面图。给地图面上的着色实质上就是给其对偶图的顶点的着色。任何平面图顶点着色时，四种颜色够用了，那么任何地图着色时，四种颜色也一定够用。这也就证明了地图四色猜测也是正确的。
7、具体图色数的确定
当ω＝1时，色数一定是1，即有γ＝1＝ω；
当ω＝2时，若图中有奇圈，则色数是3，即有γ＝3＝ω＋1，因为这种情况下图中的圈（奇）中，对于任一个K2团，都有一条不可同化道路，所以有γ＝ω＋S＝2＋1＝3；若图中没有奇圈，色数则是2，即有γ＝2＝ω；
当ω＝3时，若图中有奇轮，则色数是4，即有γ＝4＝ω＋1，因为这种情况下图中的轮（奇）中，对于任一个K3团，都有一条不可同化道路，所以有γ＝ω＋S＝3＋1＝4；若图中没有奇轮，色数则是3，即有γ＝3＝ω；
当ω＝4时，其色数总是4，即有γ≡4，因为ω＝4的图，当色数大于4时，图就不再是平面图了（见图3）。
8、图值函数色数的界
线图的密度是等于图的最大度，所以线色数的界是：Δ≤γ线≤ ；全图的密度等于图的最大度加1，所以全色数的界是：Δ＋1≤γ全≤ ；平面图的面色数等于其对偶图的顶点着色色数，所以，平面图面色数的界也是：γ平面≤4；平面图的整图的密度是max（d线度＋d面度）＋1，所以其色数的界是：max（d线度＋d面度）＋1≤γ整≤ ；从以上可以看出，图值函数的密度只与图的线度或面度有关，即ω函数＝f（d线度，d平面图的面度），所以图值函数色数的界是：f（d线度，d平面图的面度）≤γ图值函数≤ 。
9、四色猜测是正确的
从以上证明可以看出，平面图的四色猜测和地图的四色猜测都是正确的。密度是4的平面图的色数一定是4；密度是3时，若图中有奇轮，其色数是4，否则是3；密度是2时，若图中有奇圈，其色数是3，否则是2；密度是1时，色数也一定是1。任何地图都是平面图，任何地图着色时，其色数都不会大于4。


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