1.6　逆定理的证明

欧拉想解出的并不只是柯尼斯堡七桥问题，他还想解出更为一般化的问题。如果能将问题一般化，其解法自然也能套用在柯尼斯堡七桥问题上。

在研究问题时，使用例子帮助思考是一件很重要的事。如果没有一个具体的例子，就很难思考一般化的情况。仔细思考例子还可以帮助自己加深理解，毕竟示例是理解的试金石。

不过，只思考一个相对特殊的例子，对我们来说并没有什么帮助。重要的是深入思考，尽可能从具体例子延伸到一般化的情况。欧拉在论文的最后写出了他的结论。

◎　◎　◎

“欧拉在论文的最后写出了他的结论。与奇数座桥连接的陆地块数分以下三种情况。

·如果大于 2 块，就不可能不重复地走完所有桥

·如果刚好有 2 块，就可以从中任择一块作为起点，不重复地走完所有桥

·如果是 0 块，不管以哪块陆地为起点，都能不重复地走完所有桥

这和我们刚才得出的结论一样，对吧？”

“哥哥，反过来会怎样？”尤里突然提高了嗓门。

“反过来？”

“刚才哥哥说如果一个图可以一笔画成，那么它必定有 0 个或 2 个奇点，可是反过来呢？我们可以说如果一个图有 0 个或 2 个奇点，则一定能一笔画成吗？”

“可以。”

“为什么？”尤里马上反问。

“什么为什么？”

“我们还没有证明反过来的情形。哥哥也只是观察了可以一笔画成的图的起点、终点和途经点而已吧？虽然我们讨论过可以一笔画成的图有什么性质，但是并没有讨论过不能一笔画成的图是什么样子的。说不定某些有 0 个或 2 个奇点的图并不能一笔画成。”

“哎呀！”

尤里的直觉真的很敏锐，确实如此。刚才我们证明的是如下内容。

可以一笔画成的图 有 0 个或 2 个奇点

但是，我们并没有证明反过来的命题，即

可以一笔画成的图 有 0 个或 2 个奇点

是否成立。也就是说，我们并没有证明如果一个图有 0 个或 2 个奇点，则该图一定能一笔画成。

“嗯……”我开始思考。

“对吧？没证明对吧？快证明吧！”

我陷入沉思，到底该怎么证明呢？

和尤里一起回到房间后，我在 A4 纸上画了一些图，并开始思考。

“啊，哥哥，反过来不成立！”尤里说，“因为我画出了一个没有奇点的图，这个图没办法一笔画成。”

“什么？你找到反例了？”

“你看，图 ④ 就没办法一笔画成吧？”

虽然没有奇点，但没办法一笔画成的图 ④

“这个……确实如此。”我表示认同，“顶点的次数都是 2，没有奇点，但因为图 ④ 分成了两个部分，没有连在一起，所以我们自然也没办法一笔画过所有的边。”

“就是这样。”

“嗯，分开的图没办法一笔画完，如果只考虑连接在一起的图，即任选图中两个顶点，都可以找到由多条边组成的一条路径来连接这两个顶点，那就太理所当然了，反而不怎么有趣。”

“是啊。”

“如果是这样……尤里，图 ⑤ 也没办法一笔画成。”

虽然没有奇点，但没办法一笔画成的图 ⑤

“最右边的点点点是什么？”

“图 ⑤ 中的顶点会无线延伸下去，就像 A1, A2, A3, … 和 B1, B2, B3, … 这样。”

“哇，这样也可以吗？”

“在思考一笔画问题的时候，我们并不希望这种情况出现。图 ⑤ 中各个顶点的次数确实是偶数，但因为这些点会无限延伸下去，所以没办法一笔画成图 ⑤。因此，必须加上‘顶点的个数是有限的’这个条件。”

“哎？”尤里发出了不满的声音，“既然这样，也得加上‘边数是有限的’这个条件才行啊。”

“顶点的个数是有限的，边数自然也是有限的。”

“不是这样的，图 ⑥ 中的边就有无限条。”

顶点为有限个，但边是无限条的图 ⑥

“原来如此，确实如你所说。而且，这个图 ⑥ 的顶点次数还是一个不确定的数，或者可以说次数无限大。那么，我们就把‘顶点和边都是有限的’加入条件内吧。”

问题 1-2（与问题 1-1 相反）

如果一个图有 0 个或 2 个奇点，那么该图一定可以一笔画成吗？

其中，顶点的个数和边数是有限的。只考虑所有顶点连接在一起的图。

“先不说条件了，这个问题很难吗？”尤里看着我的脸说。她的头微微歪向一边，后面的马尾辫轻轻晃动着。

“不知道……”

我又想了几个具体的例子，并试着画出相应的图。尤里也在我的旁边试着一笔画出各种图。时间在我们不断尝试的过程中静静流淌着。

“嗯，看起来可以完美证明出来。”我说，“如果一个图有 0 个或 2 个奇点，我们可以实际找到一笔画出这个图的方法，也就是所谓的构造性证明。”

“那是什么啊？”

“就是不只能证明能否一笔画出一个图，还能知道如何一笔画出这个图。我来按照顺序说明吧。”

◎　◎　◎

我来按照顺序说明吧。

首先，将图分成“有 0 个奇点”和“有 2 个奇点”两种情况。当有 2 个奇点时，暂且添加 1 条边连接这 2 个奇点，使这个图成为有 0 个奇点的图。这么一来，我们只要证明有 0 个奇点的图皆能一笔画成就行了。

之所以这么说，是因为在一笔画成有 0 个奇点的图时，所画路径最后一定会回到起点。我们先把这样的路径称为自环。因为图可以一笔画成，所以这个自环一定也包括了刚才添加的那条边。既然如此，如果我们从一笔画的自环中拿掉刚才添加的那条边，图就会变回有 2 个奇点的状态，而且这个图也能够一笔画成。

所以，我们只要考虑有 0 个奇点的图是否一定可以一笔画成即可。换句话说，就是针对只有偶点的图思考。到这里懂了吗？

◎　◎　◎

“到这里懂了吗？”我问。

“原来如此喵。我懂了……然后呢？”

“嗯。”我继续说，“刚才提到要画出自环，这一点非常重要。”

“为什么呢？”

“因为我们要用‘连接自环’的方法实现一笔画。”

“连接……自环？”

“嗯。我们先试着一笔画成只有偶点的图吧。”

◎　◎　◎

试着一笔画成只有偶点的图。

以下是我想到的一笔画成一个图的步骤。

一笔画成一个图的步骤

假设图中只有偶点，至少有一条边且边数是有限的。

从某个顶点开始，沿着边画出一个自环，我们把它称为 。

将 的边从图中移除。

接着从 的顶点中选择一个有剩余其他边的顶点。

从这个顶点开始，沿着剩余的边画出一个自环，我们把它称为 。

将 的边从图中移除。

接着从 和 的顶点中，选择一个有剩余其他边的顶点。

从这个顶点开始，沿着剩余的边画出一个自环，我们把它称为 。

将 的边从图中移除。

接着从 、、 的顶点中选择一个有剩余其他边的顶点。

照着这个顺序一直画下去，直到所有的边都被移除。

此时，将 连在一起形成一个自环，这个自环就是一笔画成这个图的路径。

“嗯？我看不太懂，所以只要随便画出一个自环，再把这些自环连接起来就可以了吗？用这么简单的方法就可以一笔画成一个图吗？”

“可以。我用图 ⑦ 来说明吧。”

试着一笔画成只有偶点的图 ⑦

“只要画出一个自环就行了吧？”尤里说着，很快便画出 A → F → E → D → C → B → A 这样的一条路径。

“嗯，没错，我们把这个自环命名为 。”

画出 A→ F → E →D→C→B→A 这个自环，并把它称为

“嗯嗯。”

“接着，将 的所有边从图中移除。”

移除自环 的边

“拿掉 的边了。”

“嗯。拿掉自环之后，图中仍然全是偶点。所以我们可以继续找出其他自环，进而实现一笔画。”

“嗯。只要用 以外的边再随便画出一条自环就可以了吗？”

“没错，不过先想想看怎么选择新自环的起点吧。我们必须从 经过的顶点中，选择一个有剩余其他边的顶点作为新自环的起点。”

“听不太懂。”

“自环 的路径是 A → F → E → D → C → B → A。接下来，我们要从这条路径经过的顶点中选择一个还有边未被移除的顶点。比方说，可以试着从顶点 F 开始再画一个自环。”

“我要画！”

尤里画出了 F → A → G → E → F 这个自环。

“我们把它称为 。”我说。

画出 F→A→G→E→F 这个自环，并把它称为

“然后把 的边移除……好像越来越空了。”

移除自环 的边

“是啊。接着再将 和 连接起来，得到自环 。”

“把自环连接起来……是什么意思啊？”

“就是以 F 为连接点，将两个自环连接起来。从自环 开始，途经顶点 F 时‘换乘’到 上。在 上绕一圈回到顶点 F 后，再回到 上，然后走完自环 剩下的路径。于是，我们就得到了一个新的自环 。”

画出一个相连的自环

“原来如此。太有趣了！”

“之后就是重复同样的步骤。也就是说，接着要画出一条自环 ，然后把它移除。我们必须从 经过的顶点中选择一个有剩余其他边的顶点作为 的起点。这里我们就选顶点 A 吧。”

“这样的话，就从顶点 A 开始，画出自环 A → B → G → A，把它当作 。这样可以吗？”

“可以。”

画出 A→B→G→A 这个自环，并把它称为

移除自环 的边

“同样，我们可以将这个自环与前面的自环相连，得到 ，并将顶点 A 当作换乘点。”

画出一个较大的自环，即

“接着，将顶点 B 当作起点 …… 剩下的边刚好就是一个自环。”

“没错。可令 B → C → D → G → B 为自环 ，然后将这些边移除。”

画出 B→C→D→G→B 这个自环，并把它称为

“边全都消失了。”

移除自环 的各边

“将前面画出来的自环全部连接起来，得到 ，这样就完成了图 ⑦ 的一笔画路径。”

连接所有自环，得到 ，便可得到图 ⑦ 的一笔画路径

“好厉害！等一下，哥哥。也有可能是这个图刚好可以用这种方法找出一笔画路径。你可以保证这种方法可以用在任何图上吗？”

“嗯，保证可以。”

“难道拿随便一个顶点当起点，都可以画出一个自环？”

“都可以。因为我们现在所考虑的图都符合‘边数是有限的’和‘所有顶点都是偶点’这两个条件。毕竟从一个顶点出发后，不可能无止境地走过无数条边。”

“因为边数是有限的？”

“没错。另外，如果没办法画出一个自环，就表示走到某个顶点 时没办法再走下去了。可以走到顶点 ，却没办法从顶点 走出来，所以顶点 是一个奇点，但这就违背了所有顶点都是偶点的条件。”

“原来如此。所以，一定可以画出一个自环……”

“没错。”

“嗯，这个我懂了。可是，刚才哥哥说的方法还是有点奇怪。你说先从某个顶点开始画出一个自环，然后把自环的边移除，之后再另外选一个顶点当作下一个自环的起点。这种方式真的可以在最后把所有的边都移除吗？”

“可以，因为还有另一个条件，那就是图中各个顶点是连接在一起的。”

“一开始的图确实是这样的，但之后的步骤中不是会把一些边移除吗？这样的话，图不是也有可能被分成两三个比较小的图吗？”

“嗯，有时确实会被分成几个较小的图。不过，这些较小的图和我们之前移除的自环之间一定会有共享的顶点。如果不是这样，一开始的图就不是各个顶点连接在一起的了。”

“这样啊……”

“所以说，我们通过这种方法便可以证明反过来也是正确的。顶点次数这种单纯的数值居然和一笔画问题有关，不是很有趣吗？”

解答 1-2（与问题 1-1 相反）

如果一个图有 0 个或 2 个奇点，那么该图一定可以一笔画成。

其中，顶点的个数和边数是有限的。

另外，仅考虑所有顶点连接在一起的图。

“这么说来……”尤里说，“肚子饿了。”

“不是才吃过东西吗？”

“刚才只喝了花草茶而已。”尤里笑着说，“谁让人家还是个正在长身体的少女呢！我去找东西吃啦。”

尤里小跑着离开我的房间。

只剩我一个人在思考。

顶点次数居然和一笔画问题有关，真是有趣。

只要计算顶点次数，就可以判定一个图是否能一笔画成。

但是……

我看了一眼桌上的参考书，以及眼前的考前计划表。

但是，我的未来又该用什么来判定呢？

高考吗？用考试分数来判定吗？但分数毕竟只是判定一个人能否进入一所大学就读的门槛而已。就算考上大学，那也不是终点。高考对我而言，对我的未来而言，究竟有什么意义呢？

“哥哥！”

尤里的叫声把我的思绪拉了回来。

“快！快过来！”

我从没听过尤里那么惊慌的叫声。

我迅速穿过客厅，跑到厨房。

妈妈晕倒了。

“妈妈！”

如果与奇数座桥连接的陆地超过两块，
便不存在满足条件的路径。
然而，如果与奇数座桥连接的陆地刚好为两块，
从这两块陆地中任选一块作为起点，
便可得到满足条件的路径。
最后，如果没有一块陆地与奇数座桥连接，
不管以哪块陆地作为起点，皆可得到满足条件的路径。
——莱昂哈德·欧拉[10]