形式陈述

在有限无向图中，欧拉迹是恰好经过每条边一次的迹；若起点等于终点，则称欧拉回路。忽略孤立顶点后，图存在欧拉回路当且仅当所有含边顶点连通且每个顶点度数为偶数；存在起终点不同的欧拉迹当且仅当含边部分连通且恰有两个奇度顶点，此时它们必须是起点与终点。多重边允许，环对顶点度数贡献 2。证明可用逐步行走并把闭合子回路拼接的 Hierholzer 构造。

直觉

每次经过中间顶点都要“一条边进入、一条边离开”，所以除开放迹的两个端点外，边在各顶点成对消耗；连通性保证所有边能被一条行程覆盖。

例子与边界

一个简单环本身就是欧拉回路。路径图只有两个端点为奇度，故有从一端到另一端的欧拉迹。两个互不相交的环虽所有顶点度数都为偶数，却不能由一条迹覆盖，说明连通条件不可省。欧拉迹允许重复顶点但不能重复边，与要求访问每个顶点一次的 Hamilton 路径不同。对有向图应改用入度、出度和平衡/可达条件。

推论与应用

欧拉迹刻画“一笔画”、街道巡检、DNA 片段组装和边遍历任务。Hierholzer 算法可在线性 $O(|V|+|E|)$$O(|V|+|E|)$ 时间构造路径，而判定 Hamilton 路径通常困难得多。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§1.8, Euler tours and degree characterization。
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Ch. 12, Euler tours and graph traversals。