12.10一个连通简单平面图,存在次数小于等于4的内部面,则该图能够4-面可着色
我认为这道题目是可以证明的，它并不等价于4-CC,我觉得关键的地方是这个图是简单平面图，不等价于一般的平面图。
因为G是简单平面图（只考虑地图的情况，因为可以通过收缩去掉所有的桥，桥不影响面着色），因此其对偶图G*有一些特殊的性质——任意两个面最多只有一条公共边，同时G*无桥，利用这个性质进行下面的证明。
我们再讨论一下G*，因为G有小于等于4的内部面，因此G*存在4度顶。可以证明G*除该4度顶以外还至少有一个顶的度数小于等于5（这个非常重要），设其为u, 现在证明G*-是连通图即可。
以下我只讨论一种情况：就是d(u)=5的情况，其余的情况同理可证。
采用反证法：假设G*-u不连通，则其至少存在两个连通分支，而任意一个连通分支中都至少包含u领域中的两个顶（因为没有桥），因此如果存在连通分支数只可能为2，再证明这个也是矛盾的，如果连通分支数为2，则其中必有一个连通分支包含u领域中的两个顶点。这样导出的矛盾是——G*中存在两个面公共边的数目为2,上面已经分析了这个是不可能的。（考虑包含那两个点和 u的面与相邻的面（但不一定是外部面）是不是有两条公共边，利用了不连通的假设）
回到原题。
采用归纳法对G*的顶点数进行归纳。采用Heawood的思路，归纳的时候，删除顶点时就是上面说的那个至少为5-度的顶点。（保留那个度数小于4的定点）（删除后图的性质是不改变的）
在学校机房上的网，可能错字会比较多，不好意思，不知道我这个证明是不是正确？
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 计算机考研交流 』 → 12.10那道图论题目的一点发现（大家讨论一下）
(订阅本版)
2006/12/12 20:32:00
新浪微博
12.10那道图论题目的一点发现（大家讨论一下）
