[讨论]与网友“中山野鬼”一段讨论记录

雷明85639720

与网友“中山野鬼”一段讨论计录
雷  明
（二○一二年五月六日）
5月3 日：网名为““中山野鬼”的朋友以题为《平面图三色的疑惑》的贴子提出了一个度全为偶数的极大图的色数是3的证明问题：“我目前无法完整证明，任意极大可平面图，即任意子面都是三角形的可平面图，可三色着毕的充分必要条件是，所有顶点的边为偶数。附带性质是，顶点数目一定是偶数。”
5月3日我回复：我认为你这个问题是一个“一笔画”的问题。所有顶点的度都是偶数的图，一定是一个可“一笔画”的图形；既是一个极大图，当然每一个面均是三边形，是3—圈，有三条边；该极大图顶点同化（不相邻顶点凝结为一个顶点的过程）的最终结果一定是一个完全图K3，其着色时一定要用三种颜色；所以你说的这种各顶点度均是偶数的极大图着色时一定也只用三种颜色就够了。不满足你这个各顶点的度均是偶数的条件的极大图着色时，就不能保证三种颜色可以够用的。雷明
5 月3 日“中山野鬼”回复：谢谢你的关注。你的一笔划的思路很有新意，不过“该极大图顶点同化（不相邻顶点凝结为一个顶点的过程）的最终结果一定是一个完全图K3”这个我无法理解。“其着色时一定要用三种颜色”这个很正常，至少有一个三角形，自然需要三色。但这个很上面你说的一笔划没什么联系，我如此认为。
5 月4 日我又回复：1、你说的图是一个极大图，说明该图的密度（图中最大团的顶点数）就是 3，着色时至少要用三种颜色；2、各顶点都是偶数，说明该图中以任何顶点为轮心的轮都是偶轮；3、偶轮着色时三种颜色一定够用了，等于轮的密度3（奇轮的密度虽然也是3，但其色数却是4）；4、综合以上三点，你说给出的图——各顶点的度均为偶数的极大图，着色时的色数一定是3。我只能给出这样的证明，我想这个证明应该没有什么问题。你可以让别人看一看。上一回复我只所以联系到了一笔画问题，主要是我想到了你这个图可以一笔画出。我认为能一笔画出的图一定能“同化”成一个顶点数与它的密度相同的完全图，但这一点我却给不出证明，也请你想一想，给以解决。正八面体就是你所说的图，图中每个顶点均连有4 条边（偶数），以每个顶点为轮心的轮都是4—轮（偶轮），的却正八面体在给顶点着色时三种颜色就够用了。而正四面体则是各顶都是奇度的极大图，图中的轮均是奇轮（3—轮）着色时必须用四种颜色。
5 月4 日“中山野鬼”又回复：希望你能理解，我是对极大平面图的顶点着色。而不是面着色。任意顶点，最小的度为4.最大可以无限大。关于您说的“团”的概念，我不是太明确，如您有空，是否可以解释的细些。谢谢。
5 月4 日我再回复：我说的也是顶点着色呀。多面体也有顶点呀。任何多面体都对应有一个图的。完全图Kn就是一个团，团内的任两个顶点都是相邻的。一个图中可能有很多个团，其中必有至少一个是顶点数最多的，这个团就是最大团，最大团的顶点数就是图的密度，这些都是图论里的常识和专业术语。雷明
5月4 日我进一步回复：你说的度全为偶数的极大图的度当然最小是4 ，最大可能到无穷，顶点数当然也是任意多的。如果有一个顶点的度是2 （也是偶数）但这个图一定不是极大图了。雷明

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