半欧抗图的判定定理 定理15.2无向图G是半欧拉图当且仅当G是连通的,且G中恰有两 个奇度顶点。 证明充分性。设G的两个奇度顶点分别为u0和vo, 对G加新边(u0,v),得G′=GU(uo,), 则G是连通且无奇度顶点的图, 由定理15.1可知,G为欧拉图, 因而存在欧拉回路C’,而C=C′-(o,vo)为G中一条欧拉通路, 所以G为半欧拉图。定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两 个奇度顶点。 证明 充分性。设G的两个奇度顶点分别为u0和v0， 对G加新边（u0,v0），得G ＝G∪(u0,v0)， 则G 是连通且无奇度顶点的图， 由定理15.1可知，G 为欧拉图， 因而存在欧拉回路C  ，而C＝C -(u0,v0)为G中一条欧拉通路， 所以G为半欧拉图。 半欧拉图的判定定理