oo Proof: Let C be a Hamilton circuit of G(V, E) Then o(c-sss for each nonempty proper subset s of v Why? .o Let us apply induction on the number of elements of s s=1, ☆ The result holds %o Suppose that result holds for sEk 冷Let|S|=k+1 .o Let S=s Utv), then SEk .o By the inductive hypothesis, a(C-sss 冷VCS)=V(Gs) %o Thus C-s is a spanning subgraph of G-s y Therefore olG-Sso(C-SSISVVVAV❖ Proof: Let C be a Hamilton circuit of G(V,E). Then (C-S)≤|S| for each nonempty proper subset S of V ❖ Why? ❖ Let us apply induction on the number of elements of S. ❖ |S|=1, ❖ The result holds ❖ Suppose that result holds for |S|=k. ❖ Let |S|=k+1 ❖ Let S=S'∪{v}，then |S'|=k ❖ By the inductive hypothesis, (C-S')≤|S'| ❖ V(C-S)=V(G-S) ❖ Thus C-S is a spanning subgraph of G-S ❖ Therefore (G-S)≤(C-S)≤|S|