Euler 道判定 | Codeboy's Blog

形式陈述

设 $G$ 是至少含一条边的有限无向图，允许平行边与自环，且自环对度数计 $2$ 。令 $V_+=\{v:\deg(v)>0\}$ 。存在欧拉回路，当且仅当 $V_+$ 中所有顶点位于同一个连通分量，并且每个顶点度数均为偶数。

存在起终点不同的欧拉迹，当且仅当非孤立部分连通，并且恰有两个奇度顶点。这两个奇点必为路线的起点与终点。因而允许闭合与不闭合两种情况时，判定可合并为：非孤立部分连通，奇度顶点数为零或二。

这里判断顶点可达性时，删除自环并合并平行边得到同顶点集的简单图；两图的连通分量相同，因此可使用上述简单图连通性的定义。这个化简只用于判连通，统计度数和构造欧拉迹时仍保留每条原边的独立身份。

必要性来自边端配对。中间顶点每次进入都要离开；闭合时起点最后也补齐配对，开放时则在两个端点各留一个未配对边端。一条迹无法跨越不同连通分量，所以全部含边顶点必须连通。

先证明全偶度情形的充分性。从任一含边顶点沿未用边行走，直到不能继续。只要尚未回到起点，每次到达当前顶点时，已用边在该点共消耗奇数个边端，而总度为偶数，因此必有未用边可以离开。最终只能停在起点，得到闭合子迹。

删除这条子迹用过的边，每个顶点的剩余度仍为偶数。如果仍有未用边，原图连通性保证已有子迹上有顶点接触未用边；从该点再走出一条闭合子迹并插入原路线。每次至少消耗一条新边，有限次后覆盖全部边。

若恰有两个奇点 $s,t$ ，临时增加一条具有独立身份的边 $st$ ，所有度数就变偶数。对增广图构造欧拉回路，再在新增边处切开并删除该边，便得到原图从 $s$ 到 $t$ 的开放欧拉迹。

直觉

奇偶条件控制每个转接站能否把“进入”和“离开”配平，连通条件控制各站是否属于同一张可行走的网络。两者分别解决局部与整体障碍，缺一不可。

充分性证明同时解释了为什么不能只随便走一条路线就宣布成功：第一次闭合时可能还有其他边。Hierholzer 的关键动作是插入剩余闭合子迹，而不是从头丢弃已有结果。

例子与边界

取顶点 $a,b,c,d$ ，边集为 $\{ab,ac,bc,ad,bd\}$ 。度数分别是 $(3,3,2,2)$ ，奇点为 $a,b$ 。路线

a,c,b,a,d,b

依次使用 $ac,cb,ba,ad,db$ ，恰覆盖五条边，从奇点 $a$ 出发并在奇点 $b$ 结束。这给出了实际存在的图和轨迹，而不只是一个度数序列。

若旁边再放一个独立三角形，总奇点数仍为二，但不存在覆盖两部分的单条迹。两个互不相交的圈也说明“全偶度”单独不充分。与此不同，额外添加孤立顶点不产生待走边，不影响存在性。

星形图 $K_{1,3}$ 有四个奇度顶点，所以不能一笔走完每条边。握手引理保证奇点总数为偶数，但并不保证只有零个或两个。

若没有边而至少有一个顶点，按允许零长度迹的约定，可以停在任一顶点构成欧拉回路。无顶点空图是否接纳空路线取决于定义，应在主定理之外单独处理。有向图则应使用入度、出度与相应连通条件，不能直接用无向度数。

推论与应用

判定只需统计度数并检查含边部分连通性，时间为 $O(|V|+|E|)$ 。用邻接表、边使用标记与栈实现上述拼接过程，每条边处理常数次，构造也可达到线性时间；反复复制整条路线则未必保持这个复杂度。

欧拉问题允许重复顶点，因此与要求每个顶点只访问一次的Hamilton 问题有不同的计算性质。邮递员问题在非欧拉图上允许重复走边，以消除奇度障碍；在加权道路网络上，还需选择总代价最小的重复路线。

参考资料

Mitchel T. Keller、William T. Trotter，Applied Combinatorics，在线版，访问于 2026 年，§5.3，定理 5.13 及其构造证明。
Misha Lavrov，Start Doing Graph Theory，在线版，访问于 2026 年，第 8 章，定理 8.4 与 “Gluing cycles together”。