给个思路?

首先我觉得数学归纳法是不可行的,因为去掉v(d(v)=4)后,没有其他的4度顶点了.

如果去掉v不能用数学归纳法,那似乎就相当于证明四色猜想了~

考虑所有符合题设的平面图,如果有一个图是5色的,那么因为n<4时为4色的,所以比存在,一个极小的满足题设的5色图.它去掉一个顶点就是4色图,这时去掉哪个度数小于4的顶点,仿照heawood的定理的证明可以证明G是4色的.所以这个极小的图是不存在的.所以所有满足题设的图都是4色的.

大致思路如此.灵感来自搜到的一篇文章,但是现在找不到.

:)

PS：Heawood定理中用的是“G-v的每个连通分支中都还有度数不超过5的顶点”，而这一点是由定理11.12（即，简单平面图中必有度数不超过5的顶点）保证的。
我不知道如何由题设证明“G*-v的每个连通分支中都还有度数不超过4的顶点”。

嗯。明白了。这个办法好！：）

“面Heawood”定理，
这个思路真是妙啊。

Heawood定理的思路应该是：
“G”的每个连通分支中都存在不超过5度的顶点，
不是“G-v”吧。

而G*连通，只需证明G*中存在不超过4度的顶点。

你再看看Heawood定理的证明？
证明中有一句“设G_1=G-v，则G_1是k阶图，由归纳假设，G_1是5可着色的”。
如果要直接“仿Heawood定理的证明”（而不使用carroty的方法），那么就要“设G*_1=G*-v，则G*_1是k阶图”，可下一步，我们没法证明G*_1仍满足题设（即，我们没法证明G*_1中仍有度数不超过4的顶点），从而没法“由归纳假设”说明G*_1是4可着色的。不是吗？

为啥要在G* - v中找度数不超过4度的顶点？
我假设的就是n = k (k >= 4)时，结论成立（是4-可着色的）。

已知：对任意k阶简单平面图G，如果G中有度数不超过4的顶点v，则G是4可着色的。
求证：对任意k+1阶简单平面图G'，如果G'中有度数不超过4的顶点v'，则G'是4可着色的。

这才是正确的“归纳步骤”。
你的证明相当于将已知条件放大到了“对任意k阶简单平面图G，G是4可着色的”（这正是carroty说的，“相当于在证明4CC了”）。

“已知：对任意k阶简单平面图G，如果G中有度数不超过4的顶点v，则G是4可着色的。”
为什么要把“如果G中有度数不超过4的顶点v”
放在“平面图G”的后面，我放前面了。

我是这么考虑的：

首先找出满足下面三条性质的平面图，
1。连通。
2。无桥。
3。存在度数不超过4的顶点。
然后在这个范围内进行讨论。

命题：“这类图”是4-可着色的。
证明：
对n作归纳。
(1)n <= 4时，显然成立。
(2)设n = k(k >= 4)时成立，当n = k + 1时，
G中显然存在度数不超过4的顶点v，设G_1 = G - v,
G_1是k阶图，由归纳假设知，G_1是4-可着色的，
下面证G。
。。。

知道“G - v”是k阶的以后，
由归纳假设就可以得出G - v的每个连通分支是5-可着色的了，
为什么还要知道“G - v的每个连通分支中都还有度数不超过5的顶点”？

你的倒数第二句：“G_1是k阶图，由归纳假设知，G_1是4-可着色的”是错的。
我再问一遍，你的“归纳假设”是什么（请完整叙述）？

我再叙述一下“归纳法”原理。
归纳法原理是把待证看成一个与自然数一一对应的命题序列P(1),P(2),....
以本题为例，归纳法是把原题所成这样一个命题序列。
P(1):如果一个1阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。
P(2):如果一个2阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。
......
P(n):如果一个n阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。

你需要做的是：
首先证明P(1)。这是简单的。
然后证明P(n)=>P(n+1)。你在证明"P(n)=>P(n+1)"时，你所能使用的“归纳前提”是P(n)，也即，“如果一个n阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。”而你却说“G_1是k阶图，由归纳假设知，G_1是4-可着色的，”。请问，“由归纳假设”如何能从“G_1是k阶图”推出“G_1是4-可着色的”？

同理，Heawood定理的证明构造性的。如果我给你一个20阶简单平面图G，你是可以按Heawood定理的证明来找出一个5着色方案的。如果你试着做一下，就会明白为什么要为什么还要知道“G - v的每个连通分支中都还有度数不超过5的顶点”了。

我错了。:(

我的归纳假设是：
具有1, 2, 3这3个性质的平面图是4-可着色的。
我把“含有不超过4度的顶点”放在G的前面，
是想把它当作G的一个性质来使用，
但问题在于，不能保证在G - v中仍有4度顶点，
那么G - v就不再具有这个性质了，
也就不能使用归纳假设了。

这两天，我在考虑如果可以证明：
所有的简单平面图中都至少
存在一个不超过4度的顶点，
就可以用归纳假设了。
不过不久就发现了正20面体这个5-正则的平面图。:(

对于“G*是4-可着色的”这个命题，
也没有想出其它思路来证明。

我发现我对“数学归纳法”的理解
只是停留在“使用”这个阶段，
并没有从动态的角度去考虑过。

这个“递归”的类比真是不错。
对于Heawood定理，
我现在才有了一个比较清晰的理解：
实际上对于所有的自然数n，
都要证明这个n阶平面图是5可着色的。
只不过用归纳法把它简化成2步了。
但对于一个具体图的着色，还是一个从n到0的过程。
考虑20阶的平面图，要证明它是5-可着色的，
那么在G - v的每个连通分支中，
都要证明对于这些较小的n来说，命题是成立的。
这个过程一直向下推到“基底”。

我现在明白了，为什么在G - v的每个连通分支中
还需要5度顶点了，谢谢。:)

对于这个思路，
我开始想用G中那个次数不超过4的面，
根据Heawood定理的思路，
来归纳证明G是4-面可着色的。
但实际上它和“证明G*是4-可着色”的错误是一样的。
把这个面收缩掉后，就无法找到次数不超过4的面了。

又仔细看了一下，发现没看懂。
思路中是在说G，还是G*呢？
从“度数小于4的顶点”来看是在说G*，
而前面“所有符合题设的平面图”好像又在说G。
还有“仿照Heawood的定理的证明”，
能不能具体的说一下，
我现在对这句话特别敏感，呵呵。

我的意思就是先把他转化成G*,然后对G*进行讨论

所谓的仿照heawood的证明只是仿照它对5度顶点的讨论,对4度顶点的讨论也是成立的.

我觉得证明使用的是归谬法,所以,不需要去掉一个4度顶点后还有4度顶点.另外,可以把假设做的更确切一些,比如去掉一个4度顶点以后是4色图,而这样的四色图肯定是存在的.

你的想法呢?我不是很懂你的意思~

:)

    你把你的证明完整地写出来（后面“仿Heawood”的部分就不用写了）试试？：）

    我理解的你的证法是这样：
    设 S = { G | G是简单平面图，且G中有不超过4度的顶点，且G不是4可着色的}。下面证明 S 是空集。反设S不是空集，那么令H是S中顶点数最小的一个图。设v是H中度数不超过4的一个顶点。则“H-v必是4可着色的”（但这句话不对，你可以根据“H是S中顶点数最少的一个图”推出“H-v必然不属于S”，但没法接着推出“H-v必是4可着色的”）。

你的证明方法其实是“数学归纳法”的另一种形式（即，利用“良序集的非空子集必有最小元”的性质，通过证明“该子集没有最小元”来证明“该子集为空”。我们知道，它和“归纳法原理”是完全等价的）。

不过这道题真的证得出来吗？我好像找到了反例。。。请看看对不对。

因为G为连通的简单的平面图，所以G的平面嵌入为地图。要证明G是4-面可着色的，即证明G的对偶图G*为4-可着色的。还有一个条件就是δ(G*)<=4。
完全图K5好像完全满足G*的条件啊，但是K5的色数为5啊，这是怎么回事？

K_5不是平面图（所以K_5的对偶图也不是平面图），所以它不符合命题的前题条件，不是“反例”。：）

证明：因为一个地图是k-面可这色的当且仅当它的对偶图是k-可着色的，所以只需要证明G*是4-可着色的。

下面证明G*是4-可着色的：
若|V（G*）|<=4，显然G*是4-可着色的；
当|V（G*）|>4时：
G中存在次数小于等于4的内部面=>G*中存在顶点v，d(v)<=4，
(1)若与v相邻的顶点色数小于4，则显然G*是4-可着色的；
(2)若与v相邻的顶点色数等于4，则顺时针方向记这4种颜色为1，2，3，4，其分别对应的与v相邻的顶点记为v1，v2，v3，v4。取H={v1，v3}，然后作如下搜索：
依次检查H中的顶点，若与其相邻的涂有1，3颜色的顶点不在H中，则将该顶点添加到H中，然后重新对H执行该搜索；直到所有与H中顶点相邻的涂有1，3颜色的顶点都在H中为止。
则显然p(H)=1或2，
(2_1)当P(H)=2时，对v1所在的H中的连通分支作如下调整：1换成3，3换成1，此时对v涂1，则G*是4-可着色的；
(2_2)当p(H)=1时，则H并{v}中必有经过v的1，3组成的圈，且v2，v4必定一个在该圈外，一个在该圈内（由标记时的方法得）。
设H’={v2，v4}，对H’作如下搜索：
依次检查H’中的顶点，若与其相邻的涂有2，4颜色的顶点不在H’中，则将该顶点添加到H’中，然后重新对H’执行该搜索；直到所有与H’中顶点相邻的涂有2，4颜色的顶点都在H’中为止。
则P(H’)=2（因为H’被1，3组成的圈割断了），对v2所在的H’中的连通分支作如下调整：2换成4，4换成2，此时对v涂2，则G*是4-可着色的。

综上，G*是4-可着色的，故G是4-面可着色的。

证明：因为一个地图是k-面可这色的当且仅当它的对偶图是k-可着色的，所以只需要证明G*是4-可着色的。

下面证明G*是4-可着色的：
若|V（G*）|<=4，显然G*是4-可着色的；
当|V（G*）|>4时：
假设|V（G*）|=k时，G*是4-可着色的，现证明|V（G*）|=k+1时，G*是4-可着色的：
G中存在次数小于等于4的内部面=>G*中存在顶点v，d(v)<=4，由于|V（G*-v）|=k，所以G*-v是4可这色的。现在讨论G*：
(1)若与v相邻的顶点色数小于4，则显然G*是4-可着色的；
(2)若与v相邻的顶点色数等于4，则顺时针方向记这4种颜色为1，2，3，4，其分别对应的与v相邻的顶点记为v1，v2，v3，v4。则只需要证明v可涂1，2，3，4中某一色即可。
取H={v1，v3}，然后作如下搜索：
依次检查H中的顶点，若与其相邻的涂有1，3颜色的顶点不在H中，则将该顶点添加到H中，然后重新对H执行该搜索；直到所有与H中顶点相邻的涂有1，3颜色的顶点都在H中为止。
则显然p(H)=1或2，
(2_1)当P(H)=2时，对v1所在的H中的连通分支作如下调整：1换成3，3换成1，此时对v涂1，则G*是4-可着色的；
(2_2)当p(H)=1时，则H并{v}中必有经过v的1，3组成的圈，且v2，v4必定一个在该圈外，一个在该圈内（由标记时的方法得）。
设H’={v2，v4}，对H’作如下搜索：
依次检查H’中的顶点，若与其相邻的涂有2，4颜色的顶点不在H’中，则将该顶点添加到H’中，然后重新对H’执行该搜索；直到所有与H’中顶点相邻的涂有2，4颜色的顶点都在H’中为止。
则P(H’)=2（因为H’被1，3组成的圈割断了），对v2所在的H’中的连通分支作如下调整：2换成4，4换成2，此时对v涂2，则G*是4-可着色的。

综上，G*是4-可着色的，故G是4-面可着色的。

首先，若4色猜想成立，则本题显然成立。
其次，如果这道题的结论成立，对于任意一个图G，取其中某个内部面上的点v，在v所属的内部面内添加两点v1，v2，连接v和v1，v1和v2，v2和v，则vv1v2构成了次数为3的面，此时G是4-面可着色的，将G面着色后再删除v1，v3，则G还是4-面可着色的。

就得到了下面这个结论：

本题有解当且仅当4色猜想成立，教材上的习题12.6.(2)，12.7.(2)，小书习题5.1.4(2)，5.1.5(2)，5.1.12成立当且仅当4色猜想成立。且小书习题5.1.4(2)，5.1.5(2)，5.1.12的答案全部错误！

然后我专门去书店看了下其它教材中关于4色猜想的讲解，很多说道：它在1976年被两个美国人用计算机算出，而其中一本这样说道：美国人计算的是1900种情况，究竟是否有其它情况尚在研究中。可见4色猜想的证明是不严格的，故北大老师在90年后的教材中仍然说4色猜想没被彻底解决。

汗。。这么大一片错题居然这么多年没被改过来。。。
发现的人强！

关于它与4CC等价性的证明，我觉得也可以用对偶图的方法：假如该命题成立，那么任何有度数不超过4的顶点的简单平面图都是4可着色的。对任意简单平面图G*，在任意某个内部面上加入一个新顶点v，把v与该内部面上任意两个顶点相连，则得到的新图H满足题设。从而H是4可着色的，且该着色方案对G同样适用。这就证明了4CC。

我觉得你可以写信给刘田老师，说明你的发现！：）