什么是极大平面图？

雷明85639720

什么是极大平面图？
雷  明
（二○一五年十月份十八日）

我在学习徐俊杰先生的《四色问题新证明方法要点》一文后，在评论中说，地图是一个3—正则的平面图，其对偶图一定是一个极大平面图，其每个面都是一个三角形面。1234567—回复说：“徐先生说的三次平面图是包括 2—连通3—正则平面图G的，而图G的对偶图并不是极大平面图！”
当我把一个2—连通的3—正则的平面图的对偶图画出来（见我的《谁说2—连通的3—正则平面图的对偶图不是极大图呢？》，网址是：）后，他回复却说“千万不要忘记‘极大平面图’的定义——设G是简单平面图，a和b是图G中任意两个不相邻的顶点。如果图G 在增加一条ab 边后，会形成非平面图，则称图G为极大平面图。所谓‘简单平面图’，是无重边（或平行边）的图！”来否定我画的图。但我的图是符合他所说的“a和b是图G中任意两个不相邻的顶点。如果图G 在增加一条ab 边后，会形成非平面图，则称图G为极大平面图”的呀。而他的这个回复中，最后一句“所谓‘简单平面图’，是无重边（或平行边）的图！”则有些强求了。
道底什么是极大平面图，我们抄录几个文献上的定义如下：
1、卡波边柯的《图论的例和批例》中对“极大可平面图（Maximal planar graph）”的解释是“一个可平面图是极大可平面的，如果在G中增加任何边都导致一个不可平面图。”
2、王朝瑞的《图论》中说：“设G为平面图，如果任意两个互不邻接的顶点u，v，使得G＋（u，v）成为不可平面图，则称G是最大可平面图（maximal planar graph）。”
3、沙特朗的《图论导引》中说：“图G称为是极大平面的（maximal planar），若G是平面的，且在G的任意两个不邻接的顶点之间添加一条边即可产生一个非平面图。极大图的另一种表述方式是：如果G是平面的，但G不是其他任何平面图的一个生成子图。对于1≤n≤4，仅有的n阶平面图是Kn。因此，图9.8的所有图都是极大平面的，如果把一个阶为n≥3边数为m的极大平面图G画为一个平面图，则G的每个区域的边界必然为一个三角形且m＝3n－6。”
4、韦斯特的《图论导引》中则对Maximal planar graph解释为：“极大可平面图：等级阶于可平面三角剖分”，且定义：“极大可平面图是一个简单可平面图且它不是其他可平面图的生成子图。三解剖分是每个面的边界均为3—环的简单平面图。”
这四种定义都认为极大图是任增加一条边后图就会变成非平面图的图，即每一个面都是三解形面的平面图（只是所叙述的方式不同罢了）。前三个并没有说极大图一定要是简单图（即单纯图，不含环和平行边的图），而只有第四个提出了极大图是一个简单图强求。那个正确，还有待研究。但我认为前三个定义要准确一些。因为它能够包含所有地图（3—正则平面图）的对偶图。可以由此得到任何3—正则平面图的对偶图都是极大图的结论。
我以上个人的认识是否正确，请大家批评指正。
1234567—这位数字先生在指出2—连通3—正则平面图的对偶图不是极大平面图的同时，还说“现在还没有证明，以极大平面图K4为基础，逐个增加顶点，就可以形成所有的极大平面图！”难道徐俊杰先生以四个两两均相邻的区域的图（这也是一个3——正则图，其对偶图就是K4）为基础就能得到所有的3—正则平面图吗。
你不是认为徐俊杰先生的证明是正确的吗。徐俊杰先生用他逐个增加面的办法，能得到所有的三次平面图（3—正则平面图），那么我也就能用我逐个增加顶点的办法，得到所有的极大平面图。况且我所说的不但可以在极大图的面内增加顶点，而且可以在极大图的边上增加顶点，得到的图仍然是极大平面图。
徐俊杰能用他那个办法证明任何3—正则图的面都是可4—面染色的，证明了地图的四色猜测是正确的；那么，我用我的办法也就能证明任何3—正则图的对偶图——极大平面图的顶点也是可4—顶点着色的。又因为极大平面图通过去顶或减边而得到的任意平面图的色数只会减少而不会增加，这也就证明了平面图的四色猜测也是正确的。

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

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

雷明85639720

，，，，，，，，

朱明君

，，，，，，，，