楼主

习题12.10    图 4-面可着色问题 此主题相关图片如下： 然后用归纳法证明G*是4-可着色的 请问怎么用归纳法证明..    收藏   分享   顶(0)    关闭广告显示

	第2楼

这道题以前版上讨论过很长时间，没有的得出答案 有人甚至给出了“该题等价于4色猜想”的证明 我们去问北大的刘田教授，他说这题是可以证的，但是证明过程很难，他们决定在新版中简化这道题。 到目前为止，我没有看到或想到这题的正确证明，同时建议你先不要管这道题了（因为太难了）……

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	第3楼

谢谢Logician版主 我昨天的那思路最后发现如果正确则也是可以用来证四色定理.主要是归纳时没有细想.今天发现原来在d(v)=5时就已经有问题了.最后发现如果能够证明同色的必属于同一连通分支则没有问题.. 但证明这个完全没有思路... 嗯,我现在决定不管了..

	第4楼

以下是引用Logician在2007-11-21 18:05:00的发言： 这道题以前版上讨论过很长时间，没有的得出答案 有人甚至给出了“该题等价于4色猜想”的证明 我们去问北大的刘田教授，他说这题是可以证的，但是证明过程很难，他们决定在新版中简化这道题。 到目前为止，我没有看到或想到这题的正确证明，同时建议你先不要管这道题了（因为太难了）…… 我证了一下,大概我也没证对吧,那就问一下错在哪好了... 用归纳法证明G是4-面可着色的:设r为G中面数 1.当r=1时,显然G是4-面可着色的. 2.设当r=k时结论成立,即G是4-面可着色的,可以推出G*是4-可着色的    当n=k+1时,G中含有小于等于4的内部面知存在v属于V(G*)中有d(v)<=4,则与v相邻的顶点至多用了3种颜色,因此在四种颜色中总能找到一种给v着色,又V(G*-v)=k,由归纳假设知G*-v是4-可着色的,因此G*是4-可着色的,因为G是简单连通图,G中无环,则G*是连通无桥图,即G*是地图,由定理12.13,得到G**是4-面可着色的.又G连通,由定理11.17知,G**同构于G,因此G是4-面可着色的.

----------------------------------------------
不许偷懒~!

	第5楼

"由归纳假设知G*-v是4-可着色的" 这句不对，因为G*-v中未必还有小于等于4的内部面，所以归纳假设没法之间用……

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	第6楼

以下是引用Logician在2007-11-23 0:03:00的发言： "由归纳假设知G*-v是4-可着色的" 这句不对，因为G*-v中未必还有小于等于4的内部面，所以归纳假设没法之间用…… 不是内部面,是顶点啊,因为是相对于G*说的... 当r=k时即n*=k,有G*是4-可着色的 然后当r=k+1时,即n*=k+1时,|V(G*-v)|=k+1-1=k,那么G*-v就是4-可着色的...

----------------------------------------------
不许偷懒~!

	第7楼

归纳假设是“若H*为k阶平面图，且H*中有度数小于等于4的顶点，则H*是4-可着色的” 当你从G*中删去了一个度数小于等于4的顶点v后，能否保证G*-v中还有这样的顶点（从而能够使用你的归纳假设）呢？

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	第8楼

恩,我已经知道错在哪里了.也有人跟我说过了. 谢谢了哦~

----------------------------------------------
不许偷懒~!