相关定理 定理:设哈密顿图G=V,E>,对于V1cV,且V1≠中,均有 p(GV1)≤|V,其中,p(G-V1)为G∽V1的连通分支数。 证明 设C为G中任意一条哈密顿回路。 当V1中顶点在C上均不相邻时,p(CV达到最大值Vl 当V1中顶点在C上有彼此相邻的情况时,均有: p(C-v1)<V1. 所以,有p(CvV1)≤ 而C是G的生成子图,所以有 pG-V1)≤p(CcV1)≤。 说明 该定理只是哈密顿图的必要条件,不是充分条件。 1515 相关定理 定理: 设哈密顿图G = <V, E>, 对于∀V1 ⊂ V, 且V1 ≠ φ, 均有 p(G - V1) ≤ |V1|, 其中, p(G - V1)为G-V1的连通分支数。 证明: 设C为G中任意一条哈密顿回路。 当V1中顶点在C上均不相邻时, p(C-V1)达到最大值|V1|; 当V1中顶点在C上有彼此相邻的情况时, 均有: p(C-V1) < |V1|。 所以, 有 p(C-V1) ≤ |V1|。 而C是G的生成子图, 所以有 p(G-V1) ≤ p(C-V1) ≤ |V1|。 说明: 该定理只是哈密顿图的必要条件, 不是充分条件