今天看《Python算法教程》的时候，遇到一个归纳法证明的问题，本来以为归纳法比较简单，但今天的这个证明还有有些开阔思路的地方。问题描述：你可以在某平面上画画一张不含任何交叉边线的图（planar）。该图周边所围成的区域与其外围（无穷大）的范围形成了一组区域（regions）。如果我们分别用V, E, F来表示图中的节点、边与区域的数量，那么欧拉公式认为在平面图中，V-E+F=2。请用归纳法证明。
一般的思路
我们可以尝试对E应用归纳法，然后像内部节点计数的实例一样“向后”推导归纳步骤。其基本情况的设置并不重要（如E=0或者E=1），所以我们假设公式对E=1是成立的。这里考虑任何一种带E条边的平面图的连通图，我们尝试删除某一条边，并假设删除后的这个更小的图依然处于联通状态。由于边的数量减少了一条，势必会有两个区域合二为一，区域的数量也要减一。于是 V-(E-1)+(F-1)=2，这与我们想要证明的公式是等价的。接下来，我们考虑删除一条边之后，图结构不联通的情况。我们可以针对每个联通分量应用该归纳前提，只不过这里会产生两个无限的区域，因此需要做一些相应的抵消的处理。
当然，我们也可以对F或者V应用归纳法。
双重归纳法的思路
首先证明 证明对于任意树，V+F=E+2。
- 当只有一个节点的时候，显然成立。其中 V=1, F=1, E=0。
- 假设对于n（n>1）个节点的树，V+F=E+2。
- 当节点数为n+1的时候，考虑n到n+1的过程，第n+1的节点应为叶子节点，则有E增加1，V增加1，F不变（为1）。此时 (V+1) + F = (E+1) + 2 依然成立。
然后证明 欧拉公式的成立 - 对于任意的树，有 V+F=E+2。
- 假设 对于有n个面（F=n）的图，有V+F=E+2成立。
- 当图的面变为n+1的时候，存在一个面f，该面与 最外的无穷大的面 相邻，否则，该图为一棵树。对于f，其存在一个环路，又因为原图为连通图，则去掉f的任意一条边，所得的图依然是连通图。此时，该图的面减少1为n，边减少1。由归纳假设可得，V+F=E+2。
结束语
这里没有给出严格的证明，只是提供了一个思路。
这个双重归纳法，提醒我们化简问题可以使思路更清晰，不要总想着一步搞定。