哥尼斯堡七桥——Euler欧拉定理证明

昨天和同学复习图论，深入讨论了欧拉定理，有了相对透彻的理解，我希望写下来，我的博客就是我的笔记本，记录学习的点点滴滴而已。

定理5.1   设G为非空连通图，则G为 Euler图  <=> G中无度为奇数的顶点。

文字版我仔细的解释和理下思路。 

证明

=> ：令C = u0 e1 u1 e2 u2 ... ue (ue  = u0 )为G的一Euler环游 ，起点为u0 。则对任一顶点v ¹ u0  ，当v每次作为内部顶点出现于C时，C上有二边与v相关联。由于C上包含了G的所有边且不重复，因此d(v)=偶数。类似地，d(u0)=偶数。

 <=：反证，假设存在非空连通图，它的每个顶点的度都是偶数，但却不是Euler图 。在这种图中选取G使其边数最少（这种图的特殊之处是：每个点的度都是偶数的连通图，但是不是欧拉图的边数最少的图，也就是再少一条边就是欧拉图了）。由于 d(G) ³ 2，G包含圈（因为如果存在叶子节点，那么必然有顶点的度为奇数）。令C为G中的最长闭迹（根据定义，那么这个闭迹就是一个Euler图了）。由假设，C不会是 Euler环游。因此G - E(C)中一定有一分支G’ 使e(G’)>0（因为G不是Eluer图，那么C仅仅是最长闭迹，所以一定有边不在这条闭迹上，因此剩下的补图中边的个数一定大于0）。由于C本身为 Euler图，（由定理的必要条件知）C中每个顶点的度都是偶数，因此G’中无度为奇数的顶点（因为G是所有顶点的度都是偶数的非Euler图,对于每个顶点的度来说，偶数减去偶数，还是偶数）。但e(G’) < e(G)（这是显然的，因为G中去掉C中的边才是G’）由G的选择知，G’中含一 Euler环游 C’。 又，由于G连通，C与C’至少有一公共顶点（因为G是连通的，G’中每个点的度都是偶数，它们符合Eluer闭迹的条件，这些点肯定是在C’中的，不然怎么能叫最长闭迹呢），设为v，不妨设它同时为它们的起点。于是，CC’是G的一闭迹，其长大于C的长，矛盾。

注：这是我和同学讨论后我们的思路，或许红色字体解释的部分没有严谨的证明，欢迎指正和交流。