关于欧拉图猜想的证明

“一个连通图是欧拉图■图中所有顶点都是偶顶点。 “我们先证明如果一个图是欧拉图，那么它的所有顶点都是偶顶点。 “这点证明很简单。如果一个图是欧拉图，那么从图中任一顶点出发，

能不重复地一笔画回到这一点。这是一条欧拉回路，这条回路进出图中的每个顶点都是偶数次，并且进出的边都是不同的。所以，图中的每一个顶点都是偶顶点。

“现在再来证明，如果一个连通图的所有顶点都是偶顶点，那么这个图一定是欧拉图。

“证明的方法是：对给定的所有顶点都是偶顶点的连通图，具体找出一条欧拉回路来。这条回路找出来了，就证明这个图是欧拉图了。

“为了使大家容易理解，我结合一个具体的图来讲。

{ewc MVIMAGE,MVIMAGE, !16000290_0066_1.bmp}

“假设我们有一个连通图，它的所有顶点都是偶顶点（例如图 8—8）。我们任取一个顶点记作 DA。从 A 出发，如图 8—8 下走出一条边不重复的路：从 A 沿任一边走到另一顶点，记作 B。因 B 是偶顶点，必定还有一条和 B 关联的边还没走过，我们从这条边走到 C。同理，由于 C 也是偶顶点，所以和 C 关联的边中也一定还有一条未走过的边，我们沿这条边走到另一顶点 D。仿此做下去，由于经过一个顶点的时候，进出的边数成双，所以这条路只要到达一个不是 A 的顶点，就一定还有一条和这顶点关联的未走过的边，我们可以从这条边出去。因为图中的边数是有限的，我们每次所走的边又应是不同

的，所以这条路不能无限止地走下去，而必须在某一顶点停止。这停止的顶点不能是 A 以外的顶点，因为对 A 以外的顶点，路线经过它时有一条进去的边，由于它是偶顶点，必然还有一条边未走过，从而可从这条边走出去。可见这条路必须在顶点 A 停止。即我们将走出一条回路，不妨把它记作 P（在图 8—8 中，p＝ABCDBEFA）。

“假如 P 已走遍图中的所有边，而且因为我们走的边都是先前没走过的，可见这些边都是不同的。这样 P 就是一条欧拉回路，从而我们证明了这个图是欧拉图。

“假如图中还有一些边没被 P 走到。由于图是连通的，从第六章定理 1 知道，P 中有某个顶点（例如图 8—8 中的 E），关联某条未走过的边。由于E 是偶顶点，所以和 E 关联的未走过的边的数目一定仍是偶数条。同理，在图中任一顶点关联的未走过的边都是偶数条。这样，从 E 出发，正像从 A 出发一样，又可找到一条回路 P′，它走过图中一些不同的未走过的边再回到 E

（见图 8—9，在这图里，p′＝EGHE）。

{ewc MVIMAGE,MVIMAGE, !16000290_0068_1.bmp}

“现在我们可从 A 出发，沿 P 的一部分先走到 E（如图 8—9 为 ABCDBE），到了 E 后，沿 p′走回 E（EGHE），然后继续走完 P 剩下的一部分回到 A（EFA）。这样，由 P 和 p′合起来的回路 q 就比 P 走过更多的边了（图 8-9 中 q＝ ABCDBEGHEFA）。如果 q 走遍整个图，它就是一个欧拉回路，我们也就证明了给定的图是欧拉图。如果 q 还没走遍全图，我们又能仿照上面的办法把 q 再扩大。由于图的边数有限，扩大有限次后，一定能找到一条回路，它走遍了整个图的边，而且由于每次走的时候，都是走未走过的 G 边，所以这条回路中的边都不相同。可见最后这条回路是一条欧图 8-9 拉回路。这也就证明了所给的图是欧拉图。

“这样，我们就得到了一个定理：

〔定理 2〕一个连通图是欧拉图■这个图所有的顶点都是偶顶点。“回顾我们探索怎样的一个图是欧拉图的过程，我们再一次看到如何通

过特例的实验，归纳总结规律，提出猜想，最后再给以证明的过程。这种探索问题的办法是很有用的。今后大家在学习中应当学会使用这种办法。

“应用定理 2，我们很容易判别一个图是否欧拉图。这只要看看所给的图中是否有奇顶点就可以了。现在我们回到哥尼斯堡七桥问题上来。在这个问题中，能否设计一条散步路线从陆地的某处出发，走遍每座桥恰好一次再回到原出发点，相当于问图 8-2（b）是否欧拉图。由于这个图中有 4 个奇顶点，所以它不是欧拉图，可见这样的散步路线是设计不出来的。这也就是欧拉那篇论文的答案。

“定理 2 有许多实际应用。下次讲座我将介绍如何利用定理 2 来研究游迷宫问题，探索一个比方法一少走冤枉路的方法。今天的讲座就到这里为止。”

听完这次讲座，大家都感到收获很大。因为有些同学过去玩过一笔画游戏，以前大家老是一个图一个图去试，不懂得去探索规律，现在有了刘老师介绍的定理 2，随便拿一个图就能很快判别它是否能一笔画回到原出发点了，而且还知道怎样去画它。此外，大家还从这件事得到很大的教育，学习了实验——归纳——猜想——证明的探索问题的方法。从这里，大家更觉得刘老师循循善诱，既教给大家知识，又教给大家研究问题的方法，他们对刘

老师更加爱戴了。下面是刘老师留下的练习。

练习三

下列各图，哪些图能从任一顶点出发，走遍图中每条边恰好一次再回到原出发点？
一个至少有两个顶点的连通图，假如要从顶点 A 出发，走遍图中的每条边恰好一次到达另一顶点 B（这种从 A 到 B 所走过的路即欧拉路），这个图各顶点关联的边数应有什么特征？请你作出猜想并加以证明。

（1）{ewc MVIMAGE,MVIMAGE, !16000290_0070_1.bmp}

（2）{ewc MVIMAGE,MVIMAGE, !16000290_0071_1.bmp}

（3）{ewc MVIMAGE,MVIMAGE, !16000290_0071_2.bmp}

在哥尼斯堡七桥问题中，请你添一座桥，使得能从一个小岛出发，走过每座桥恰好一次到达另一小岛。
下图表示一个十五座桥的问题。图中的英文字母表示陆地。问：

能否从某地出发，走过每座桥恰好一次再回到该地？
能否从某地出发，走过每座桥恰好一次而终止于另一地？

{ewc MVIMAGE,MVIMAGE, !16000290_0071_1.bmp}