Euler 道判定

沿 Euler 迹经过一个中间顶点时，每次进入都必须配对一次离开，所以中间点度数为偶数；只有开放迹的起点和终点各留下一个未配对边端。这个奇偶条件只是局部守恒，连通性负责排除另一个完全没有被走到的含边分量。充分性证明可从不断沿未用边走出的闭回路开始，再把剩余回路拼接进去。

一条非平凡路径恰有两个奇度端点，因此具有 Euler 道。两个互不相交的环虽然所有顶点度数均为偶数，却因非孤立部分不连通而无法一笔画完。

度数序列为 $(3,3,2,2)$ 的连通图若存在，恰有两个奇度顶点，Euler 迹必须从其中一个出发、在另一个结束。若在此图旁再放一个独立三角形，所有非零度顶点不再位于同一连通分量，即使总奇点仍为二，也不存在覆盖全部边的一条迹。孤立点不含待走边，因此判定中只要求删去孤立点后的部分连通。

握手引理公理库握手引理Handshaking lemma有限无向图中所有顶点度数之和等于边数的两倍。保证奇度顶点总数为偶数，连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。与度数配对共同构成判定条件。实际构造可用 Hierholzer 算法在线性时间生成Euler 迹公理库欧拉迹Eulerian trail · Eulerian path恰好一次经过每条边的迹。；与Hamilton 路公理库Hamilton 路与 Hamilton 圈Hamiltonian path · Hamiltonian cycle恰好一次访问图中每个顶点的路径，以及首尾相接的这种圈。不同，这里要求每条边恰用一次而允许重复顶点。邮递员问题则在非 Euler 图上补边，使奇点得以配对。