离散数学无向哈密顿图的一个必要条件鲁 定理132设无向图G=<V,E>是哈密顿图,对于任意V1c且 V1≠,均有p(G-V1)≤1 证设C为G中一条哈密顿回路 (1)p(C-1)≤|1 (2)p(G-V1)≤p(C-V1)≤1(因为CcG) 推论设无向图石=<V,E>是半哈密顿图,对于任意的vV 且类均有 p(G-V1)≤|1+1 证设厂为从到v的哈密顿通路,令G=G∪(,),则G为 哈密顿图.于是 p(G-V)=p(G-V1-(l,)sp(G-V1)+1sv|+111 无向哈密顿图的一个必要条件 定理13.2 设无向图G=<V,E>是哈密顿图，对于任意V1V且 V1，均有p(G−V1 )  |V1 | 证 设C为G中一条哈密顿回路 (1) p(C−V1 )  |V1 | (2) p(G−V1 )  p(C−V1 )  |V1 | （因为CG） 推论 设无向图G=<V,E>是半哈密顿图，对于任意的V1V 且V1均有 p(G−V1 )  |V1 |+1 证 设 为从u到v的哈密顿通路，令G = G(u,v)，则G为 哈密顿图. 于是 p(G−V1 ) = p(G−V1−(u,v))  p(G−V1 )+1  |V1 |+1