欧拉定理证明
引文：嵌入 (embedding)
将图G "嵌入" 一个平面後得到的它在该平面的一个 "嵌入" W， 则:W上的顶点一一对应G上边的端点, W中的边一一对应G上的简单弧, 并满足:
1.W中任意一条弧的端点对应G中一条边的顶点.
2.W中任意一条弧上的点和G中顶点不相关
3.W中任意两条弧的交点对应G中边的顶点.
简单弧 (simple arc)
平面内无环路连续曲线.
图的对偶(dual graph)
G*是图G的"对偶" , 则: 在平面内被图分隔开的每一个区域中取一个点, 并将这些相临区域中取得的点用边相连, 得到的图是G*.
( 对偶的性质是对称的, 用 "G*" 表示G的对偶,则G** = G)
如图: G' 与Ｇ互相对偶.
连通图 (connected graph)
如果无向图所有顶点互相可达, 则它是连通的.
生成树 (spanning tree)
一棵遍历图所有顶点的树.
翻译的欧拉公式 V + F - E = 2 的19种证明方法
（原文： Nineteen Proofs of Euler's Formula ） http://www.ics.uci.edu/~eppstein/junkyard/euler/
"我"的话:
1. 若论思想性、精简、严密， 原文远胜。 所以赘述， 乃体谅中文资料难求之苦。
2. 欢迎修改
注:
1> 带引号的词语, 我也不确定.
2> 斜体词语, 后面有解释,
3> 未完成
注2:
1> V + F - E = 2 是拓补学重要公式 (原型被推广到了凹多面体 V + F - E = C ): . 欧拉公式还有很多
2> 以下证明, 有三个重要的数学模型被使用, 证明中我给出了简述, 其实不严密. 有兴趣可以再查资料.
它们是: Jordan curve theorem, dual graph, graph embedding
"结合2棵生成树"原理:对于任二维平面内"嵌入"的连通图G, 它的一个"对偶"是G*.(取G中每个面的中点, 以及G外一点, 相临面各连一边成为G的"对偶": 图G*)
我们假定: G*中由G相临面连成的边, 只被G中这两个面交线分隔. 那么:
1. G中的环,一定切断G*
2. G中的树,一定不会切断G*
(上面两个性质的证明用到拓补学的一个定理, Jordan curvetheorem: 这个定理对我们来说是没什么疑问, 简述其旨如下:
一条简单封闭曲线分平面为两部分.
但据说这个定理在数学史上的证明大费周折)
证明:
取G的生成树T, 则T不含环, 且T中边相对于G的补集 T'同样不含环 .
因为 T' 没有切断 G*, 所以 T' 的对偶仍是生成树. T的边数是 (V-1) , (T')* 的 边数与 T' 相同, 是 (F - 1)
可以证明: 这两棵生成树边数的和是G的边数: (V- 1) +(F - 1) = E
"简单归纳"注: 作者声明自己不喜欢这样的证明.
"It is to my mind unnecessarilycomplicatedand inelegant;"
证明１:(归纳面）
将一个图先 "嵌入" 二维平面得到图G.
当G只有一个面时 : E(1) = V(1) - 1 + F(1) - 1
当G有N个面时,
设: E(N) =V(N-1) - 1 +Ｆ(N-1) - 1
我们去除一条G中两个面的一条临边, 得到G有 N-1个面时
E(N-1) = E(N)- 1
V(N-1) = V(N)
F(N-1) = F(N)
故: E(N-1) =V(N-1) - 1 + F(N-1) - 1
丛而归纳出欧拉公式成立
证明２：（归纳顶点）
将一个图先 "嵌入" 二维平面得到图G.
当G只有一个顶点时 (一个简单环 )
F(1) + V(1) - E(1) = (E(1) + 1) + 1 - E(1) = 2
当G有N个顶点时, 假设结论成立
我们去除一条G中两个面的一条临边, 得到G有 N-1个面时 ,面和边各减少1. 故结论成立
证明3：（归纳边）
和上面的方法一个思路
略.
"缩小面的归纳"证明:
当凸多面体只有一个面时, V(1) + (F(1) - 1) - (E(1) - 1) = 0 显然成立.
假设当有N个面时这一性貭仍然成立. 这时我们,从凸多面体上取下一个面. 这时多面体成为了一个 "开口的容器".
我们这时在不影响面数的前提下缩小这个 "开口", 直到为一个点.于是得到一个新的凸多面体.
设这个凸多面体比原来少了 M 个顶点, 则这M个顶点在 "开口" 上,因此这个多面体比之原先, 又减少了M条边.
这样假设在N - 1 时成立
"电中性"证明：
如图
用一种方法放置, 使图的边都不在水平面上, 这样就产生了最高点U, 最低点L. 在凸多面体的顶点放正单位电荷, 边中点放负单位电荷, 面中点放正单位电荷.
以下证明, 可以中和除了U, L所在位置外的电荷: 从上往下看, 我们让所有电荷在水平面 "逆时针" 运动一次到相临面, 那么:
1> U, L 不动 2> 不考虑U, L, 进入一个面的电荷是该面边数 e的一半减一. ( e / 2 - 1), 负电荷多一 , 其他电荷除了面中点的一个正电荷全部移出.
故除U,L 完全中和.
得证
“ 用‘嵌入’ 法中和”
和上一法不同， 我们首先得到凸多面体的在二维平面的一个 "嵌入"(embedding) ：如图： 首先, 我们旋转图使之没有一个是竖直的. 之后, 将在每个面和顶点中点上放一个正电荷， 在每条边中点上放一个负电荷。 (注意: 多面体的"嵌入", 将平面分成几个区域则原多面体有几个边, 因此图外的面上也放一个正电荷.) 下一步我们规定电荷移动的方向: (1) 移动边上的电荷到右方顶点. (2) 移动面上的电荷到面最右的顶点. (3) 图外面的正电荷不动. 这样, 除了最左边的顶点和图外的顶点上的两个电荷全部中和.