MathLabs

解法：欧拉的度数论证(1736年)

第 5/6 步：从配对论证到欧拉的精确准则
上一步下一步
通俗地说

刚才的配对论证直接证明了一个方向:欧拉路径的奇数度陆地绝不会超过两个,因为只有起点和终点才可能剩下一座落单的桥。更费工夫的——也是卡尔·希尔霍尔泽(Carl Hierholzer)在1873年严格证明的——是反方向:拥有 00 或 22 个奇数度顶点不仅是必要条件,实际上也足以保证这样的路径存在,并且有一种构造方法绝不会留下落单的桥。

#{v∈V:deg⁡(v) mod 2=1}∈{0,2}\#\{v \in V : \deg(v) \bmod 2 = 1\} \in \{0, 2\}
详细分析

上一步已经直接证明了欧拉准则中'仅当'的一半:如果一个连通图存在恰好经过每条边一次的路线,那么奇数度顶点的个数要么是 00(若路线回到起点,则为闭合回路),要么恰好是 22(一条开放路径,其两个奇数度顶点必须是它的起点和终点)。

反过来——对连通图而言,00 或 22 个奇数度顶点也是充分的——是更难的一半。欧拉在1736年的论文中断言了这一点,但没有给出完整证明;卡尔·希尔霍尔泽于1873年给出了完整的构造性论证,展示了如何通过拼接闭合回路来构造这样一条路线(Biggs, Lloyd & Wilson 1976, 第2章)。

两个方向合在一起,就给出了一个精确的判别法——#{v∈V:deg⁡(v) mod 2=1}∈{0,2}\#\{v \in V : \deg(v) \bmod 2 = 1\} \in \{0, 2\}——适用于任何连通图,这正是为什么这是一条解决所有可能桥梁布局的真正定理,而不仅仅是关于某一座城市的观察。

本步骤用到的知识
欧拉回路定理
常见错误. 总度数为偶数(两步之前的握手引理)对任何图而言都自动成立,单凭这一点并不能证明什么;精确的准则需要的是奇数度顶点的实际个数,这比总和仅仅是偶数要严格得多。