相关定理 推论:设半哈密顿图G=<V,E>,对于任意V1CV,且V1≠φ,均有: pGV1)≤|V+1 证明:设P是G中起于u终于v的哈密顿通路 令G”=GU(u,v)(在G的顶点UV之间加新边)。显然,G”为哈密 顿图 由前述定理可知p(GV1)≤N 于是,有p(GV1)=p(GV1(u,v)≤p(G'1)+1≤V+1 1616 相关定理 推论: 设半哈密顿图G = <V, E>, 对于任意V1 ⊂ V, 且V1 ≠ φ, 均有: p(G-V1) ≤ |V1|+1。 证明: 设P是G中起于u终于v的哈密顿通路。 令G’ = G∪(u, v)(在G的顶点u,v之间加新边)。显然, G’为哈密 顿图。 由前述定理可知 p(G’-V1) ≤ |V1|。 于是, 有 p(G-V1) = p(G’-V1-(u,v)) ≤ p(G’-V1)+1 ≤ |V1|+1