组合数学：用图论的方法证明多面体的欧拉公式

我在前面的文章“如何证明椭圆积分的非初等性”说“十九世纪真是数学的黄金时代啊，各种新思想涌现”。组合数学则是一个直到20世纪才成熟的领域，直到现在仍是由孤立的碎片组成。组合数学是数学中最朴素的分支，几乎不需要前置知识，而图论又是组合学中最朴素的分支，却又与数学其他部分有着丰富联系。在前面文章为什么正多面体只有五种介绍过用擦除法证明欧拉公式，图论是一个强有力的工具，用图论来证明欧拉公式的过程给出了比欧拉公式更多的东西。

定义1（简单图）：一个图G由顶点集V、边集E,以及联系每一边的无序对（x,y）的映射构成。如果一条边的两个端点相同，这样的边称作环。如果一个顶点不关联任何边，称作孤立点。如果一个图没有环，且任意两个顶点之间只有一条边，称为简单图。

定义2（简单闭路）：图G的一条步路是顶点和边的交错序列

定义3（连通的图）：如果对图G的每一对顶点x,y，都存在从x到y的路，则称G是连通的。

定义4（树）：不含简单闭路的连通图称为树。

显然在任何连通图中可以找到含有全体顶点的的树形子图，而树的顶点数比边数多1。欧拉定理如下表述。

Euler定理：设P为满足下列条件的多面体。

（a）P的任何两个顶点可用一串棱相连接；

（b）P上任何由直线段构成的圈，把P分割成两片。

则对P来说，V-E+F=2。其中F代表面数，V代表顶点数，E代表棱数。

证明：显然，P的全体顶点和棱构成连通图，所以能找到一个树形子图包含所有顶点，设这个树为T。构造一个图G，P的每个面对应G的一个顶点，并且如果P的两个面之间的公共棱不属于T，那么G中这两个面对应的顶点就有一条棱相连。

以长方体为例，红色的就是树T，蓝色的是图G。可以证明G是连通的，这个证明涉及到更深入的内容，在此省略。现在证明G也是树。反证法，假设G不是树，即G含有简单闭路，这个圈将P分成两片，每一片至少含有一个顶点。而根据G的定义，G的简单闭路经过的P的棱都不属于T，所以T不包含所有顶点，矛盾。

这样T和G都是树，所以V(T)-E(T)=1, V(G)-E(G)=1, 所以V(T)+V(G)-(E(T)+E(G))=2。而V(T)就是P的顶点数V,，V(G)就是P的面数F，E(T)+E(G)就是P的棱数E，所以V-E+F=2。