在一个度非零的所有顶点都连通的多重图中，各顶点度的奇偶性决定了每条边能否恰好经过一次。

图、度与欧拉迹

定义与范围事实

有限无向多重图 $G=(V,E)$ 由有限的顶点集合 $V$ 和有限的边集合 $E$ 构成。每条边连接两个顶点，但不规定经过的方向。同一对顶点之间可以有多条边；自环也可以把一个顶点与其自身连接起来。简单图是不含自环和平行边的特殊情况。

之所以选择这一框架，是因为柯尼斯堡有多座桥连接同一些陆地区域：要表示这些桥，就需要平行边。本文不讨论有向图——其中的边具有方向——也不讨论加权图——其中的边会带有距离或成本等信息。

因此，底层多重图只保留关联关系：每条边连接哪些顶点。图中绘制的位置、长度和角度都不属于它的定义。这些数据在有用时可以加入模型，但对于本文研究的问题并非必需。

一条欧拉迹恰好使用每条边一次。如果两个端点不同，它就是开放的；如果回到起始顶点，它就成为欧拉回路。这里的“欧拉”描述的是边，而不是顶点。

每条普通边有两个端点，并使其两个顶点的度各增加1。自环同样有两个端点，但二者都位于同一顶点，因此使该顶点的度增加2。按重数计数时，每条边对总和的贡献恰好为2：

$\sum_{v\in V} \deg(v)=2\,|E|$

右边是偶数。偶度顶点贡献的总和是偶数，因此奇数度数的总和也必须是偶数。而若干奇数整数之和为偶数，当且仅当其中的项数为偶数。因此，奇度顶点的数量总是偶数。

在表示一场集会的简单图中，一条边表示两个人握过手。此时，引理说明握手次数为奇数的人数是偶数。这个形象解释了引理名称的由来，但采用前述度的约定时，该证明对多重图和自环同样成立。

这一历史问题描述了由七座桥连接的四块陆地区域。问题是寻找一条恰好经过每座桥一次、且不要求回到起点的游走。

欧拉用字母表示这些区域，并用字母序列表示连续的过桥过程。在现代图论的重新表述中，每块区域成为一个顶点，每座桥成为一条边。得到的多重图有四个顶点，其度分别为5、3、3和3。它们的总和是14，恰好等于边数（七）的两倍，符合该引理。

在欧拉迹中，所有关联边都会被使用。每次经过一个中间顶点时，边都成对消耗：一条用于进入，一条用于离开。因此，开放欧拉迹只有起点和终点的度为奇数，而欧拉回路没有奇度顶点。

柯尼斯堡有四个。不存在恰好使用七座桥各一次的迹。 欧拉证明了这种不可能性，并给出了普遍的奇偶性规则；现代定理则给出完整的刻画。

考虑一个有限无向多重图，其中度非零的所有顶点都属于同一个连通分量。

必要性来自进入与离开的配对。充分性是构造性的。当所有顶点的度都是偶数时，从一个与边关联的顶点出发，沿尚未使用的边前进。不可能被困在另一个顶点：每次到达该顶点后，根据奇偶性，都会留下一条尚未使用的边供离开。因此，这条迹最终会回到起点并形成回路。

如果还有边未使用，连通性保证回路上的某个顶点与尚未使用的部分相接。从该顶点构造一条新回路，再将它插入第一条回路。重复这一操作，便可得到包含所有边的回路：这就是 Hierholzer 算法的原理。

如果恰好有两个奇度顶点，就在它们之间临时添加一条边。所有顶点的度于是变为偶数；先构造一条欧拉回路，再移除添加的边。回路随之展开成一条迹，其两个端点恰好就是那两个奇度顶点。

道路、软件依赖关系、分子和电路都可以用图表示，但若不加限定，就不能使用同一个模型。

因此，抽象的益处并不在于一种算法可以适用于所有场景，而在于把共同结构——顶点和边——与领域特有的信息分离开来，再选择其假设与所构建的图精确对应的定理或算法。

在边属于同一个连通分量的有限无向多重图中，各顶点度的奇偶性决定了每条边能否恰好经过一次：奇度顶点为零个时存在回路，恰好为两个时存在开放欧拉迹。