经典证明：不用数学归纳法直接推导平面图的Euler公式

把《三体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。