无向哈密顿图的必要条件 定理6:设G=<V,E>是无向哈密顿图,则对 V的任意非空真子集V有 p(GV)≤N1 证明:设C是G中任意哈密顿回路,当V中 顶点在C中都不相邻时,p(CV=V最大; 否则,p(CV)VC是G的生成子图,所 以p(GV)≤P(CV1)≤V.# 《集合论与图论》第18讲《集合论与图论》第18讲 8 无向哈密顿图的必要条件 定理6: 设G=<V,E>是无向哈密顿图,则对 V的任意非空真子集V1有 p(G-V1)≤|V1| 证明: 设C是G中任意哈密顿回路, 当V1中 顶点在C中都不相邻时, p(C-V1)=|V1|最大; 否则, p(C-V1)<|V1|. C是G的生成子图, 所 以p(G-V1)≤P(C-V1)≤|V1|. #