无向欧抗图的判定定理 定理15.1无向图G是欧拉图当且仅当G是连通图,且G中没有奇 度顶点。 证明若G是平凡图,结论显然成立。 下面设G为非平凡图,设G是m条边的n阶无向图, 并设G的顶点集V={v,v2,…,vn 必要性。因为G为欧拉图,所以G中存在欧拉回路, 设C为G中任意一条欧拉回路,Vv∈V""都在C上, 因而v,v连通,所以G为连通图。 又vv∈Vv在C上每出现一次获得2度 若出现次就获得2k度,即(v)=2k, 所以G中无奇度顶点。无向欧拉图的判定定理 定理15.1 无向图G是欧拉图当且仅当G是连通图，且G中没有奇 度顶点。 证明 若G是平凡图，结论显然成立。 下面设G为非平凡图，设G是m条边的n阶无向图， 并设G的顶点集V＝{v1 ,v2 ,…,vn}。 必要性。因为G为欧拉图，所以G中存在欧拉回路， 设C为G中任意一条欧拉回路，vi,vj∈V，vi,vj都在C上， 因而vi,vj连通，所以G为连通图。 又vi∈V，vi在C上每出现一次获得2度， 若出现k次就获得2k度，即d(vi)＝2k， 所以G中无奇度顶点