无向半欧拉图的充分必要条件 定理2:设G是无向连通图,则 (1)G是半欧拉图 2)G中恰有2个奇度顶点 证明:(1)→>(2):欧拉通路的起点和终点是 奇数度,其余顶点都是偶数度. 2)→(1):在两个奇数度顶点之间加1条新边 所有顶点都是偶数度,得到欧拉回路从欧 拉回路上删除所加边后,得到欧拉通路# 《集合论与图论》第17讲《集合论与图论》第17讲 9 无向半欧拉图的充分必要条件 定理2: 设G是无向连通图,则 (1) G是半欧拉图 ⇔ (2) G中恰有2个奇度顶点 证明: (1)⇒(2): 欧拉通路的起点和终点是 奇数度,其余顶点都是偶数度. (2)⇒(1): 在两个奇数度顶点之间加1条新边, 所有顶点都是偶数度,得到欧拉回路.从欧 拉回路上删除所加边后,得到欧拉通路. #