欧拉回路

定理：一个无向图 ( G ) 存在欧拉回路，当且仅当：
1. ( G ) 是连通的；
2. ( G ) 中每个顶点的度数均为偶数。

证明：
- 必要性：
- 连通性：若存在欧拉回路，则该回路必须经过所有边，因此所有顶点通过边相连，图必然连通。
- 偶数度数：在回路中，每次进入一个顶点后必然要离开，因此每个顶点的入度等于出度，总度数为偶数。

• 充分性（构造性证明）：
• 从任意顶点 ( v ) 出发，沿未访问的边行走，直到无法继续。由于所有顶点度数为偶数，最终必回到 ( v )，形成一个回路 ( C )。
• 若 ( C ) 未覆盖所有边，则存在顶点 ( u ) 在 ( C ) 中且仍有未访问的边。以 ( u ) 为起点构造新回路 ( C’ )，将 ( C ) 和 ( C’ ) 合并。
• 重复合并过程，直至所有边被包含，最终得到欧拉回路。

欧拉路径

定理：一个无向图 ( G ) 存在欧拉路径但不存在欧拉回路，当且仅当：
1. ( G ) 是连通的；
2. ( G ) 中恰好有两个顶点的度数为奇数，其余顶点度数均为偶数。

证明：
- 必要性：
- 连通性：欧拉路径需经过所有边，故图必须连通。
- 奇数度数顶点：路径起点和终点的度数为奇数（进入和离开次数差1），其余顶点度数为偶数（进入等于离开）。

• 充分性：
• 设两个奇度数顶点为 ( u ) 和 ( v )。添加边 ( (u, v) )，此时所有顶点度数为偶数，存在欧拉回路。
• 从该回路中移除边 ( (u, v) )，得到一条以 ( u ) 和 ( v ) 为端点的欧拉路径。

结论：
- 欧拉回路：图连通且所有顶点度数为偶数。
- 欧拉路径：图连通且恰有两个顶点度数为奇数。