半欧抗图的判定定理 定理15.2无向图G是半欧拉图当且仅当G是连通的,且G中恰有两 个奇度顶点。 证明必要性。设G是m条边的n阶无向图,因为G为半欧拉图, 因而G中存在欧拉通路(但不存在欧拉回路), 设「=von"1…Ym1mm.为G中一条欧拉通路,V≠vmno vv∈(G,若在「的端点出现,显然d()为偶数, 若咋在端点出现过,则d(为奇数, 因为「只有两个端点且不同,因而G中只有两个奇数顶点。 另外,G的连通性是显然的。定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两 个奇度顶点。 证明 必要性。设G是m条边的n阶无向图，因为G为半欧拉图， 因而G中存在欧拉通路(但不存在欧拉回路)， 设Г＝vi0 ej1 vi1…vim-1 ejmvim为G中一条欧拉通路，vi0≠vim。 v∈V(G)，若v不在Г的端点出现，显然d(v)为偶数， 若v在端点出现过，则d(v)为奇数， 因为Г只有两个端点且不同，因而G中只有两个奇数顶点。 另外，G的连通性是显然的。 半欧拉图的判定定理