1. 引言
本文提及的图都是有限简单无向图。假设
。令
表示m个图类。如果
可以被分解为m个集合
,使得对于
,子图
属于图类
,那么我们称其为图G的一个
-分解。为简单起见,我们用F,I,
和
分别表示图类森林,独立集,最大度为k的图和最大度为k的森林。文中的三角形指3-圈。如果两个圈或面至少有一条公共边,则称它们相邻。如果两个圈或面至少有一个公共点,则称它们相交。
著名的四色定理 [1] [2] 告诉我们每一个平面图都存在
-分解。并且根据无圈染色问题的相关研究,在1976年,Borodin [3] 证明了每一个平面图都存在
-分解。此后,在1990年,Poh [4] 证明了每一个平面图都存在
-分解。但是,早在1969年,Chartrand [5] 等人就找到了不存在
-分解的平面图。
另一方面,2008年,Raspaud和Wang [6] 证明了每一个不含距离小于2的三角形或对于某个
,不含k-圈的平面图都存在
-分解。此外,在不久后Chen,Raspaud和Wang [7] 成功证明了每一个不含相交三角形的平面图都存在
-分解。最近,Dross和Montassier [8] 证明了每一个不含3-圈的平面图存在
-分解。
本文证明了如下结果:
定理 每一个不含4-圈和5-圈的平面图都存在
-分解。
接下来给出文中的一些基本记号。G中点v的度数用
表示。我们分别用k-点,
-点和
-点表示度为k的点,度至少为k的点和度至多为k的点。同理定义k-面,
-面和
-面。称G中的
-点为大点,否则为小点。因此v的
-邻点称为大邻点,否则称为小邻点。称v在F中的邻点为F-邻点。用
表示v的大邻点的个数。对于
,若f的边界点按顺时针方向排列依次为
,则可记作
。并且令
表示以
为公共边与f相邻的面,其中
且i对n取模。对于m-面
,若
的度数为
,则可记f为
-面。假设v为k-点,令
为按顺时针方向排列的邻点,则
表示以
和
为边界与v关联的面,其中
且i对k取模。
对于集合
,令
表示在G中删去所有的S中的点及其关联的边所得的图。对于与V不交的点集S,令
表示在G中加上S中的点所得的图。对于与E不交的边集
,令
表示在G中加上
中的边所得的图。
2. 定理证明
2.1. 极小反例的结构性质
假设
为上述定理点数最少的极小反例。显然,G是连通的,否则我们可以找到一个点数更小的极小反例。首先我们给出G的一些结构性质。
断言 1 G中不存在
-点。
证明 假设v为G中的
-点。根据G的极小性可得,
存在
-分解。如果
,那么我们可将v放入F。假设
,若它的两个邻点都在F中,则可将v放入
。否则v至少有一个邻点在
中,此时我们可将v放入F。因此我们总能得到G的
-分解,矛盾。
断言 2 G中的3-点至少相邻一个大点。
证明 假设
且它的邻点都为小点,即
-点。根据G的极小性可得,
存在
-分解。如果v的三个邻点中至少有两个在
中,那么我们可将v放入F。如果它的三个邻点都在F中,那么我们可将v放入
。现在假设v恰好有一个邻点u在
中。如果u至多有一个F-邻点,那么我们可将u放入F,v放入
。否则因为u为小点,它至多有四个
-邻点,此时我们可将v放入
。因此我们总能得到G的
-分解,矛盾。
断言 3 G中不存在6-面
使得
是三角形,且
,
,或当
只有一个大邻点时,
,
,
。
证明 不妨设
为G中满足断言1的6-面,令
分别为与
关联的第三个点,且令
的第四个邻点为
。则由断言2,
为大点,
。令
,则
中不存在4-圈和5-圈。由G的极小性可得,G存在
-分解。我们要证明在下列所有情况下我们都可以得到G的
-分解。在下列情形中,若
在
中,则将
放入
可能会增加
中点的度数,此时因为
是小点我们可以将它
放入F。
· 若
都在F中,则我们将
放入F,
放入
。
· 若
恰好有一个点在
中。设
在
中,则我们将与
关联的另外两个点放入F,将与f关联的另外四个点放入
。
· 若
恰好有两个点在
中。设
在
中,则我们将与
关联的另外两个点放入F,将与f关联的另外两个点放入
。
· 若
都在
中。由于
为
中的三角形,则至少有一个点在
中。若
在
中,则将
放入
,将
放入F,若
在
中,
,则我们将与
关联的一个点放入
且将其余与f关联的点放入F。
因此在任意情况下G都存在
-分解,矛盾。
断言 4 若
为
-面,
为三角形,且与
关联的第三个点为小点,则
。
证明 设
为上述6-面,令
的第三个邻点和与
关联的第三个点分别为
。令
,则由G的极小性,
存在
-分解。当
时,我们可以很容易地将
的
-分解扩充到G。
首先假设
在F中。若
中至多一个属于
,则可将
放入
。否则可将
放入F。现在假设
在
中。若
中至多一个属于F,则可将
放入F。因此可以假设两者都在F中。若
都在
中,则同样可将
放入F。若两者都在F中,则可先将
放至
,再将
放至F。否则,首先假设
在
中,
在F中,若
至多有四个
-邻点,则可同样将
放至
。若有至少五个
-邻点,则可将
放至F,
放至
。因此可得
在F中,
在
中。
同上分析可得
和
一定在F中,
,且
一定在
中。若
,则
至多有四个
-邻点。因此我们可以将
或者
放入
。
放入F。因此我们总能得到G的
-分解,矛盾。
断言 5 设
为G中的
-面,其中
为三角形,
。令与
关联的第三个点为
。若
为小点,
,则
中至少有一个
-点。特别地,若
或
为3-点,则
都为
-点。
证明 设
都为8-点。令
,由G的极小性可得,
存在
-分解。下面我们要证明G存在
-分解,从而得出矛盾,从而证明
中至少有一个
-点。
· 首先假设
都在F中。若
都在F中,则将
放入
。否则,由于
都是小点,可将
放入
,
放入F。
· 假设
恰好有一个点在F中,由对称性不妨设
在F中且
在
中。此时可将
放入
,
放入F。
· 设
都在
中。若
中至多有一个点在
中,则将
放入F。现在假设
都在F中。由于
中至多有一个点在
中,若
其余的邻点不都在
中,则将
放入
,
放入F。因此,
和
中都恰好有一个点在
中。
(1) 如果
在F中,则将
放入F,
放入
,
放入F。
(2) 如果
在
中,则将
放入F,
放入
,
放入F。
若
都为3-点,由对称性不妨设
。我们知道
中恰好有一个点在
中,且
中至少有一个点在F中。令
的第三个邻点分别为
。
· 设
在
中。若
在F中,则我们将
放入
,
放入F,
放入
且将
放入F。否则,
在
中且
在F中。若
在
中,则将
放入F,则我们回到了之前讨论过的情况。否则,将
放入F,同样回到之前讨论过的情况。
· 设
在
中。若
在F中,我们将
放入
,
放入F,
放入
且将
放入F。否则,我们直接将
放入F,
放入
,
放入F。
2.2. 权转移
接下来我们将应用权转移来得出矛盾。首先我们对G中的顶点和边定义初始权函数
。对于
,
;对于
,
。根据欧拉公式和握手定理可得
。
然后定义适当的权规则将初始权
通过权转移变为最终权
,使得对于每个
,有
。注意到权转移过程不会改变总的权和,因此我们可以得出如下矛盾,
,从而完成定理的证明。
设
。令
为v在平面上按顺时针方向排列的邻点。记以
和
为边界构成的面为
,
且i对4取模。设
是一个6-面,若
是一个三角形,则令
为与
关联的第三个点。
若v是一个3-点,关联一个三角形且只有一个大邻点,则称v为一个坏3-点。另外,若v是一个4-点且关联两个三角形,则称v为坏4-点。设
是一个
-面且
为三角形,
。若
是小点,
,且
或者
不都为3-点,则称f是一个坏6-面。很显然,任意两个坏6-面不相邻。
对于
,我们用
表示x转给y的权值。另外,用
表示与v关联的三角形的个数。对于任意
,用
表示与f关联的坏3-面的个数。我们的权规则定义如下:
(R1) 令
。若
,则v给每个关联的6+-面转权
。设
,若v是一个坏3-点,则v给每个关联的三角形转权1。否则,v给每个关联的三角形转权1,给每个关联的6+-面转权
。
(R2) 令
。若
,则v给每个关联的
-面转权
。当
时,令
为三角形,则
,
且
。设
,则v给每个关联的三角形转权1,给每个关联的
-面转权
。
(R3) 5-点给每个关联的三角形转权1,给每个关联的
-面转权
。
(R4) 小
-点给每个关联的面转权1。
(R5) 令v为G中的一个大点,则
(R5.1) v给每个相邻的小点转
。若v相邻一个大点u,则v给每个与v关联且以uv为边界的面转权
。
(R5.2) v给每个关联的三角形转权1。
-点给每个关联的
-面转权
。每个6-点给关联的
-面
转权
,其中
至多相邻一个与v关联的三角形。
(R6)
-面给每个关联的坏3-点转权
,给每个相邻的坏6-面转权
。
下面我们证明对于所有
,
。令
,则
。
· 设
。若
,则由(R1)和(R5)可得
。若
,假设v是一个坏3-点,则根据规则(R1),(R5)和(R6)我们可以得出
。否则,
。
· 设
。若
,则由(R2)和(R5)可得
。若
,则
。设
,则
。
· 设
,由(R3)我们可以得到
。
· 设
,由(R4)我们可以得到
。
· 设
,由(R5)我们可以得到
。
· 设
。如果
,则根据(R5)可得
。如果
,则根据(R5)可得
。
下面我们证明对于
,有
。如果
,那么根据规则(R1)-(R5)我们可以得出
。如果
,则f的边界上至多有6个坏3-点并且f至多相邻两个坏6-面。因此
。设
,有
。现在假设
,令
。接下来我们将根据
的值将证明分为以下几个部分。注意到不是坏3-点的3-点和小
-点至少给每个关联的
-面转权
。
情况 1 假设
,则有
。
情况 2 假设
,则f不相邻坏6-面。令
为坏3-点,
为三角形。则
一定为
-面。因此不管
是大点还是小点,都有
。从而有
。
情况 3 假设
。
首先假设
为坏3-点。如果
为三角形,那么
都为
-面,因此
,
。故有
。现在假设
为三角形,如果
为小点,那么
肯定为大点,因此根据规则(R1)-(R4)可得
。从而有
。假设
为大点,如果
也为大点,则根据规则(R5.1)可得
;否则
。由对称性可得
。因此
。
假设
为坏3-点。如果
为三角形,那么
都为
-面,因此有
且
,故
。现在假设
为三角形,由于
为
-面且
不为坏点,因此
,故
。根据对称性我们假设
为三角形,那么
必为
-点且不为坏点,因此
。
假设
为坏3-点。由对称性,如果
为三角形,那么
必为
-面。由于
都不为坏点,因此
且
。故
。如果
为三角形,那么
为
-面,同样我们有
且
。因此
。
情况 4 假设
。
假设
为坏3-点。根据对称性假设
为三角形,则有
。如果
为小点,那么
肯定为大点,因此根据(R2)-(R4)可得
。假设
为大点,如果
也是大点,那么根据规则(R5)有
。否则
。因此
。
假设
为坏3-点。如果
为三角形,那么根据以上讨论我们可得
且
。因此
。假设
为三角形,同样可得
且
。因此
。假设
为三角形。如果
为小点,那么
肯定为大点,因此根据规则(R2),
。由于
为
-面,
不为坏点,因此
,故
。现在假设
为大点,那么
肯定为小点。同样有
。如果
为小点,那么
肯定为大点,因此根据规则(R2),
。否则假设
为大点,如果
为三角形,那么根据规则(R2)有
,或根据规则(R5)有
。在每种情况下我们都有
。最后假设
为三角形。此时
为
-点且
为
-面。如果
为小点,那么
肯定为大点,因此根据规则(R2),
。现在假设
为大点,由于f为
-面,
。并且
为小点,那么
肯定为大点,因此根据规则(R2),
。否则
。因此总有
。
假设
为坏3-点。首先假设
为三角形,则
必为
-面,因此
且
。故
。现在假设
为三角形,同样可得
且
。因此
。
情况 5 假设
。
假设
为坏3-点。首先假设
为三角形,那么f不相邻坏6-面。并且
都为
-面,因此
且
。故
。现在假设
为三角形,如果
都为大点,那么
且
。如果
都为小点,那么
都为大点,因此根据规则(R2)同样有
且
。否则根据对称性假设
为大点而
为小点,此时
肯定为大点,因此
。故
。
假设
为坏3-点。首先假设
为三角形,那么
肯定为
-面,因此根据规则(R1),
。此时如果
为小点,那么
肯定为大点,因此根据(R3)
,故
。现在假设
为大点,根据断言4,
,此外
不为坏面,因此
。从而有
。假设
为三角形,那么
肯定为
-面且
为小
-点,因此
。此时如果
为大点,那么
肯定不为坏面且
,因此
。否则
肯定为大点,因此根据规则(R2),
。从而有
。
假设
为坏3-点。首先假设
为三角形,那么f相邻的其余面都为
-面,此时有
且
。因此
。假设
为三角形,那么此时
为
-面。如果
都为大点,那么
。否则
都为小点并且
都为大点,因此根据规则(R2),
,故
。最后假设
为三角形,如果
都为小点,那么对于
,
都为大点。根据规则(R3),
,
,因此
。现在假设
中恰有一个为小点,不妨设为
,此时
不为坏面,因此我们同样可得
,
。最后假设
都为大点,那么对于
,
都为小点。根据断言5,如果
或
都为3-点,那么
都为
-点。因此
。否则f为坏6-面,同样根据断言5,
中至少有一个点为
-点,因此根据规则(R6),
并且
,从而有
。
情况 6 假设
。对于
,令
为坏3-点,此时
为大点且
为小点。根据断言3,
为
-点,因此
,从而我们可得
。
基金项目
本文工作受到了浙江师范大学启航奖学金的资助。