定理7(证明二) 定理7:设G=<V,E>是无向半哈密顿图,则 对V的任意非空真子集V有 p(GV1)≤+1 证明二:设P是G中任意哈密顿通路,两个 端点是u与V.令G=GU(uV),由定理6有 p(GV1)≤p(G1V1)+1≤+1.# 《集合论与图论》第18讲《集合论与图论》第18讲 10 定理7(证明二) 定理7: 设G=<V,E>是无向半哈密顿图,则 对V的任意非空真子集V1有 p(G-V1)≤|V1|+1 证明二: 设P是G中任意哈密顿通路, 两个 端点是u与v. 令G1=G∪(u,v), 由定理6有 p(G-V1) ≤ p(G1-V1)+1 ≤ |V1|+1. #