1.   引言

1976年Appel与Haken等人^[1－3]宣布用计算机给出了四色猜想的“证明”，但是给出四色猜想的数学证明仍是一个尚待解决的困难问题。四色猜想的研究对象可归结于极大平面图，因此，弄清楚极大平面图的结构与构造是极为重要的。许多学者对极大平面图的结构进行了研究。文献[4,5]给出了利用纯弦圈构造极大平面图方法。2005年，Brinkmann等人^[6]给出了构造最小度为5的极大平面图的一种有效方法。2001 年，Gao等人^[7]及2011年，Bose等人^[8]对极大平面图的边翻转进行了探讨。我们知道，唯一4-可着色平面图一定是极大平面图，那么唯一3-可着色平面图的充分必要条件是什么，至今尚未解决。文献[9,10]中对唯一3-可着色平面图的临界性及三角形的相邻性做了探讨。

许进教授等人在其系列文献[11－17]中对极大平面图进行了深入的研究。许进教授在文献[13]中对(2,2)-递归极大平面图进行了刻画，同时为了给证明JT猜想做准备，得到了一个重要结果，即“对(2,2)-递归极大平面图G的长为2的路xuy实施扩4轮运算后所得到的图不是唯一4色的，其中x与y是G的两个3度顶点”。本文推广了(2,2)-递归极大平面图到(k,l)-递归极大平面图，对(k,l)-递归极大平面图的存在性及结构问题作一探讨。

本文所说的图均为无向有限简单图，平面图均指其平面嵌入。

对于一个平面图G实施扩3-轮运算是指在G的某个三角形面xyz内添加一个新顶点v，使v与x, u, y均相邻，最后得到一个阶为|V(G)|+1的平面图的过程。这个扩3-轮运算通常记为“v-xyz”。一个递归极大平面图是指从平面图K₄出发，逐次实施扩3-轮运算而得到的极大平面图。所谓一个(k,l)-递归极大平面图是指一个递归极大平面图，它恰好有k个度为3的顶点，并且任意两个3度顶点之间的距离均为l。本文对(k,l)-递归极大平面图的存在性问题做了探讨，刻画了(3,2)-及(2,3)-递归极大平面图的结构。

图 1  阶分别为4,7,10的递归极大平面图

下载: 全尺寸图片 幻灯片

首先，以如下方式依次构造一系列递归极大平面图G⁽ⁱ⁾, i=1, 2, 3, ···。其中G⁽¹⁾, G⁽²⁾, G⁽³⁾如图1(a), 图1(b)及图1(c)所示。一般地，由G⁽ⁱ⁾构造G⁽ⁱ⁺¹⁾的过程如下：

在G⁽ⁱ⁾的基础上，在面x_i+1y_iz_i里添加一个新点y_i+1，使y_i+1与x_i+1, y_i, z_i均连边，然后在所得到图的面x_i+1y_i+1z_i里添加一个新点z_i+1，使z_i+1与x_i+1, y_i+1, z_i均连边，最后在所得图的面x_i+1y_i+1z_i+1里添加一个新点x_i+2，使x_i+2与x_i+1, y_i+1, z_i+1均连边，最终得图G⁽ⁱ⁺¹⁾。

2.   (k,l)-递归极大平面图的存在性探讨

下述两个命题是显然的。

命题1　当l ≥2时，G^(l)是(2,l)-递归极大平面图。

命题2　 G^(l)的最中心的3度顶点x_l+1与x_i, y_i, z_i的距离均为l+1–i, i=1, 2, ···, l。特别地，x_l+1与外部面的3个顶点x₁, y₁, z₁的距离均为l。

图 2  命题3所述图的结构

下载: 全尺寸图片 幻灯片

图 3  命题3证明过程中出现的递归极大平面图

下载: 全尺寸图片 幻灯片

命题3　在G^(l)的外部面上添加一个新点x，使x与x₁, y₁, z₁均连边(如图2所示)，所得到的(2,l+1)-递归极大平面图的阶数最少，其阶数等于3l+2。

证明　由于任一面均可为外部面，固定(2,l+1)-递归极大平面图G的一个3度顶点为x，它的3个邻点为x₁, y₁, z₁，在此基础上逐次扩3-轮可得G。

先扩3-轮x₂-x₁y₁z₁，如图3(a)所示，这是阶数最少的(2,2)-递归极大平面图，其阶等于5=3×1+2。为了得到(2,3)-递归极大平面图，在最后一次扩3-轮时，所在的面的边界不能出现x₁, y₁, z₁，因而还得做两次扩3-轮以便出现所需要的面x₂y₂z₂，然后在面x₂y₂z₂里扩3-轮，得(2,3)-递归极大平面图(如图3(b))，其阶数最少。将这个过程进行下去，命题得证。

图 4  定理4证明过程中出现的递归极大平面图

下载: 全尺寸图片 幻灯片

定理1　存在(k,2)-递归极大平面图，k ≥2。

证明　 图3(a)给出了一个(k,2)-递归极大平面图，称x₁为其中心点，选与3度点x及x₁关联的2个三角形面进行2次扩3-轮，得图4(a)，这是一个(3,2)-递归极大平面图。在此基础上任选一个3度点v，再对与v及x₁关联的2个三角形面均扩3-轮，得图4(b)，这是一个(4,2)-递归极大平面图，这个过程进行下去，任意的(k,2)-递归极大平面图均可构造出来。 证毕

定理2　存在(k,l)-递归极大平面图，这里k ≥2, l(≥2)是偶数。

证明　由上述定理可知，存在(k,2)-递归极大平面图H, H中有k个3度顶点v₁, v₂, ···, v_k。而v_ix₁v_j是H的长为2的路，1≤i<j≤k，这里x₁是H的一个中心点，注意不会存在一个面使其边界上既含v_ix₁又含v_jx₁, i≠j。对每个v_i，选定一个与v_i和x₁关联的面v_ix₁u_i, i=1, 2, ···, k。

对每个面v_ix₁u_i代之以G^(l/2)，即面v_ix₁u_i及其内部被G^(l/2)所填充。最后所得图仍含有k个3度点，且任两个3度点之间的距离恰为l。 证毕

定理3　对奇数l ≥3，存在(3,l)-及(4,l)-递归极大平面图。

证明　令l=2s+1，在G⁽³⁾的基础上，面x₁x₂z₁被G^(s)所填充，当然G^(s)的外部面的3条边要和x₁x₂, x₂z₁, z₁x₁分别重合。同样，让x₃x₄z₃被G^(s)所填充，而让x₂x₃z₂被G^(s+1)所填充，最后所得到的图恰有3个3度顶点，并且任意两个3度顶点之间的距离均为l。这样就得到一个(3,l)-递归极大平面图。在上述得到了的(3,l)-递归极大平面图的基础上，设边界包含x₂x₃的并且包含在最后被填充进去的G^(s+1)中的一个三角形面为x₂x₃w，这时G^(s+1)中的3度顶点v与w的距离为s。再在面x₂x₃w中填充进去G^(s+1)，其的3度顶点记为v′ ，所得到的图含有4个3度顶点，任意两个3度顶点间的距离为2s+1=l。特别地，d(v,v′ )=2s+1的原因是v′ 与w之间的距离为s+1，而w与v之间的距离为s，结论得证。

本文提出如下猜想。

猜想　不存在(k,l)-递归极大平面图，这里k ≥5, l为奇数，l ≥3。

3.   (2,3)-递归极大平面图的结构

设G是(2,3)-递归极大平面图，且G的两个3度顶点分别为x和y。

若x与y之间有3条内部不交的长为3的路，则称G为A型的；

若x与y之间仅有2条内部不交的长为3的路，则称G为B型的；

若x与y之间只有1条内部不交的长为3的路，则称G为C型的。

图 5  A型的(2,3)-递归极大平面图

下载: 全尺寸图片 幻灯片

图 6  6阶的B型(2,3)-递归极大平面图

下载: 全尺寸图片 幻灯片

图 7  定理7证明里(1)中的B型(2,3)-递归极大平面图

下载: 全尺寸图片 幻灯片

图 8  定理7证明里(2)中出现的(2,3)-递归极大平面图

下载: 全尺寸图片 幻灯片

图 9  定理7证明里(2)中出现的另一个(2,3)-递归极大平面图

下载: 全尺寸图片 幻灯片

图 10  C型的(2,3)-递归极大平面图

下载: 全尺寸图片 幻灯片

定理4　A型的(2,3)-递归极大平面图G只有如图5所示的一个，它是8阶的，它也是阶数最少的(2,3)-递归极大平面图。

证明　不妨设在以{x, x₁, y₁, z₁}为顶点集合的完全图的基础上，逐步在面x₁y₁z₁的内部扩3-轮就可得到G。

在此过程中，必然要第1次出现一步，使在一个其边界上的点均不是x₁, y₁, z₁的三角形面x₂y₂z₂中扩3-轮。x₂, y₂, z₂中恰有一个点，不妨设为x₂，与x₁, y₁, z₁的距离均为1, x₂, y₂, z₂中恰有一个点与x₂, y₁, z₁或与x₂, x₁,y₁或与x₂, x₁, z₁的距离全为1，不妨设y₂与x₂, y₁, z₁的距离全为1。紧接着扩3-轮时必须考虑x₂y₁y₂或x₂y₂z₂(二者等价)，否则，如考虑面y₁, y₂, z₁，那么最终所得(2,3)-递归极大平面图中另一3度点y没有经过x₂的长为3到x的路。

可设在x₂y₂z₂中扩3-轮，增加的顶点为z₂。下一步如果在x₂z₂z₁或y₂z₂z₁中扩3-轮的话，比如在x₂z₂z₁中扩3-轮，增加顶点w，那么里面的3度顶点y(属于最终所得图)与x之间的长恰为3的且经过y₂的路是不存在的。这样就保证不了两个3度顶点之间存在3条内部不交路，因而在x₂y₂z₂中扩3-轮新增顶点为x₃，而x₃与x恰有3条内部不交的长为3的路。进一步扩3-轮是不可取的。

在构造B型极大平面图的过程中，前6个点可以设为是固定的，如图6所示。

(1) 第7个点u₁如在面y₁y₂z₁内，那么构造出来的图是先依次扩3-轮u₁, u₂, ···, u_r，再在面u_r–1u_rz₁里依次扩3-轮，轮心依次为v₁, v₂, ···, v_s，再在面v_sv_s–1u_r–1里依次扩3-轮，轮心依次为w₁, w₂, ···, w_t，最后所得图(如图7所示)是w_t与x间恰有两条内部不交的长为3的路。

(2) 第7个点在面x₂y₂y₁或x₂y₂z₁内(二者等价)，不妨设第7个点z₂在面x₂y₂z₁内。

这时如第8个点在x₂y₂z₂内，那么以后还要至少进行一次扩3-轮，且每次扩3-轮时是基于3度点及x₂和z₂围成的面(当然可以以y₂和z₂代替这里的x₂和z₂，或以x₂和z₂代替这里的x₂和z₂)。这样就保证恰有两条内部不交的路xx₁x₂y和xz₁z₂y。

如果第8个点w在x₂z₂z₁内，第9个点在x₂z₂w内，那么以后扩3-轮时点是基于3度点以及x₂和w所围成的面，其结果如图8所示。

如果第8个点w在x₂z₂z₁内，第9个点在z₂wz₁内，这时构造不出来(2,3)-递归极大平面图。

如果第8个点w在x₂z₂z₁内，第9个点在x₂wz₁内，那么总有经过逐次扩3-轮(顶点u₁, u₂, ···, u_r)之后，总有一步扩3-轮时基于一个边界不含z₁的面x₂u_r–1u_r，如图9所示。

至于C型的结构就相当松散了，在图6的基础上，在面x₂y₂z₁内陆续添点扩3-轮，但要保证扩3-轮时基于的面的边界上要包含x₂，并且有一次添点时所添的点与z₁的距离超过2，有一次所添的点与y₂的距离要超过1，这是为了使两个3度点x与y间有唯一的长为3的路xx₁x₂y。图10给出的就是一个C型的例子。 证毕

注意下述结论是显然的。

定理5　设G是(2,3)-递归极大平面图，v是G的任意一个3度顶点，则

(a)G-v是(2,3)-递归极大平面图。

(b)G-v是非相邻型的(2,2)-递归极大平面图。

4.   (3,2)-递归极大平面图的结构

设G是(3,2)-递归极大平面图，x, y, z是G的3个3度顶点，如果x, y, z中任意两个点之间都有两条长为2的路，那么G称为A型的；

如果x, y, z中恰有两对顶点，不妨设为{x, y}, {x, z}，使得x与y之间，x与z之间都有两条长为2的路，那么G称为是B型的；

如果x, y, z中恰有一对顶点，不妨设为{x, y}，使得x与y之间有两条长为2的路，那么G称为是C型的；

如果x, y, z中任意一对顶点之间只有一条长为2的路，那么G称为是D型的。

图 11  A型递归极大平面图

下载: 全尺寸图片 幻灯片

图 12  B型的(3,2)-递归极大平面图

下载: 全尺寸图片 幻灯片

图 13  C型的(3,2)-递归极大平面图

下载: 全尺寸图片 幻灯片

图 14  D型的(3,2)-递归极大平面图

下载: 全尺寸图片 幻灯片

定理6　A型的(3,2)-递归极大平面图只有一个，即图11(a)所示的7阶图。

证明　先固定前5个点，且使x永远成为3度点，如图11(b)所示。注意到3个面uv₁v₂, v₁v₂w, uv₂w的彼此等价性，为了得到(3,2)-递归极大平面图，在面uv₁v₂内添点逐步扩3-轮，保证里面最终只有1个3度点，同时在面v₁v₂w内添点逐步扩3-轮，使里面最终只有1个3度点，分别只做1次扩3-轮后所得的7阶图，如图11(b)所示。

假如在uu₁v₁里或uu₁v₂里扩3-轮的话，最终得到的图在uu₁v₁里的3度顶点与v₁v₂w里的3度顶点最多有1条长为2的路。

假如继续在uu₁v₂里3-轮的话，最终所得图在u₁v₁v₂里的3度顶点与x间的长为2的路最多只有1条。

至此定理6得证。

为了得到如图12的B型的(3,2)-递归极大平面图，确保x与另外两个3度顶点的长为2的路均有两条，在图11(a)的基础上，确保x与uv₁v₂内部的3度顶点间的长为2的路有两条，那么在uu₁v₁里扩3-轮如同上段B型的方法，而在v₁v₂w里扩3-轮时，最后一次扩3-轮所基于的面的边上仅含v₁与w中的1个即可。图13所示的(3,2)-递归极大平面图就是C型的。

对于D型的(3,2)-递归极大平面图，只需在图11(a)的基础上逐次扩3-轮，使得最终所得图的面uv₁v₂内的3度顶点y, wv₁v₂内的3度顶点z，满足|N(x)∩N(y)|=1, |N(x)∩N(z)|=1, |N(y)∩N(z)|=1即可，图14所示的(3,2)-递归极大平面图就是D型的。

注意下述结论是显然的。

定理7　若设G是(3,2)-递归极大平面图，v是G的任意一个3度顶点，则G-v是(3,2)-递归极大平面图或G-v是(2,2)-递归极大平面图。

5.   结束语

本文将文献[13]中讨论的(2,2)-递归极大平面图进行了推广，提出了(k,l)-递归极大平面图，研究了(2,3)-递归极大平面图以及(3,2)-递归极大平面图的结构。我们将会继续对(k,l)-递归极大平面图的结构及着色问题做进一步探索。