把《三体II黑暗森林》看完后，又把上学期已经放下的Proofs from THE BOOK拿出来翻了几页。当结束了数论部分进入几何学时，一些离散性的东西让整本书陡然科学了起来。前面那篇日志里的牛B证明就是我从这本书的第9章中看到的，运用线性代数的基本定理我们居然可以证明一个无从下手的图论问题！今天我又看到牛B证明了：平面图Euler公式V+F=E+2的非数学归纳法证明。以前我见到过各种Euler公式的证明，证明方法千奇百怪，其中不乏很多独具匠心的精巧证明，但它们本质上都是运用数学归纳法不断拆边重组减低规模，将复杂的平面图一点一点变得简单。在Proofs from THE BOOK的第11章，我见到了一个用半页纸写下的巧妙证明，证明方法简单、美观而有趣，读后让人会心一笑。
在介绍这个证明之前，让我们先来回顾一下什么是Euler公式。Euler公式是说，在一个由若干顶点和它们之间的一些不相交的边所组成的图中，等式V+F=E+2总成立，其中V表示顶点个数，E表示总的边数，F表示这个图分割出来的区域个数（包括一个“外部区域”，例如一个圆把平面分割为两个区域）。如图1，这个图共有6个顶点、10条边和6个区域，可以看到6+6=10+2是成立的。为了证明这个结论，考虑这个图的任意一个生成树（图1中加粗了的边）。再考虑这个图的“对偶图”：新图的每个顶点代表原图的一个区域，原图的两个区域相邻则在新图上的两个对应顶点之间连一条边（图2中的虚线部分）。接下来，我们找出原图中那些不属于生成树的边界线，把它们在新图中所对应的边加粗（图2中的加粗虚线）。容易看出，加粗的虚线是连通的，因为原图的粗线条是一棵生成树，它没有隔离出任何一块区域；同时呢，加粗虚线是没有环的，否则它将把某个原图的顶点包起来，从而原图中的加粗线条就不可能是生成树了。只需要注意到一棵树的顶点数等于边数加一，我们的结论就直接出来了：原图的顶点数就是Euler公式中的V，它等于原图生成树的边数加一；新图的顶点数就是Euler公式中的F，它等于新生成树的边数加一；而两棵生成树的边数总和正好就是原图中的E。于是呢，我们就得到了V+F=E+2。
沙发耶～
嗯嗯，还有，我也想体验一下膜拜你的感觉～～咔咔～
严肃地膜拜一下M67大牛～～说实话昨天晚上你给我讲语概第一题的时候我真的被你震撼到了～～
我真的想知道楼上是不是M67大牛的“那什么什么”。
ls。。
别人的blog地址都留下了。。 自己去看看不就清楚了。。
发现煋了
一直很喜欢这本书，但是有些地方看不懂 = =
强啊 等有空了我也买本Proofs from THE BOOK看看
话说一直想知道你博客里的图都是用什么软件或者语言画的？
someone,楼上是托儿
您的有关分形的文章通俗易懂，我很感兴趣，能继续写一些有关三维分形的文章吗？我很想知道在三维空间中如何实现分形。谢谢。
两个问题：
1. M67牛你就是dd_engi吗？
2. M67牛你GIF格式的数学公式图是用什么画的？
容易看出，加粗的虚线是连通的，因为原图的粗线条是一棵生成树，它没有隔离出任何一块区域；同时呢，加粗虚线是没有环的，否则它将把某个原图的顶点包起来，从而原图中的加粗线条就不可能是生成树了。
这段话是否已经默认了Euler定理了呢？？
@LS 没有吧
真是很精辟的证明啊！
@10楼 问题1
{obviously} false
有个问题请教下……
最近在思考四维空间里的东西……于是发觉自己三维都没搞清楚……于是现在先反思三维的……
去看了下那个 从一到无穷大
那个双苹果是不是就是四维球？
这个证明是不是不够严格？
Matrix 有没有兴趣帮助 review 一下“雪山飞壶”这篇翻译文章的完成部分？原文到9999，才刚翻译到82，巨大的工程。
Any, that’s very funny.
http://www.yeeyan.com/articles/view/xueshanfeihu/4502
好神奇!!!!
强烈赞美
DD和M67
的伟大友谊。
Orz……
哦，其实这种证法在我高中教材上面就有提示，我当时也是这么证的
立体的也可以用树做的…非常犀利..凸多面体的话直接映射成一个球面就很直观了
一直很喜欢这本书，但是有些地方看不懂 = =
大黑和小白是两只兔子，一公一母。 一天，大黑找到小白，悄悄地对他说;“小白啊，你猜我这里有几颗糖，猜对了我三颗全给你。”小白想了想，笑嘻嘻的说“我猜有五颗。”大黑也笑了，把手摊开，说道“呵呵，那大黑哥哥欠你两颗。”这本来是很美好的故事，可是因为一个结局全毁了—–小白吃完之后，没想到糖里下了蒙汗药，结果被小黑强X了。第二天，他们再次相遇。小黑“善意”地问道:昨天的糖好吃么，来，今天还有两个。小白摇摇头说:黑哥，这糖不行啊，吃了之后屁股痛啊·····知道她没事我就放心了