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|
o Theorem 5.9: Let G be a simple graph with n vertices. where n>2 G has a hamilton circuit if for any two vertices u and y of g that are not adjacent, d(u)+d(v2n 8,d(u)=d(v) u and v are not adjacent, d(u)+d(v)=6<8 But there is a hamilton circuit in the graph Note: 1)ifG has a Hamilton circuit then g has a Hamilton path Hamilton circuit.v,v,v..v.v 1 Hamilton path:V1,V2, V3,.Vns 2)IfG has a Hamilton path, then G has a Hamilton circuit or has not any Hamilton circuit 7
❖ Theorem 5.9: Let G be a simple graph with n vertices, where n>2. G has a Hamilton circuit if for any two vertices u and v of G that are not adjacent, d(u)+d(v)≥n. n=8,d(u)=d(v)=3, u and v are not adjacent, d(u)+d(v)=6<8, But there is a Hamilton circuit in the graph. Note:1)if G has a Hamilton circuit , then G has a Hamilton path Hamilton circuit :v1 ,v2 ,v3 ,…vn ,v1 Hamilton path:v1 ,v2 ,v3 ,…vn , 2)If G has a Hamilton path, then G has a Hamilton circuit or has not any Hamilton circuit
corollary 1: Let G be a simple grap with n vertices. n>2.g has a hamilton circuit if each vertex has degree greater than or equal to n/2 g Proof: If any two vertices of G are adjacent then G has a Hamilton circuit V1V2,V3y…VnV1° .s If g has two vertices u and y that are not adjacent, then d(u+d(v2n. &By the theorem 5.9g has a hamilton circuit .&K has a hamilton circuit where n>3
❖ Corollary 1: Let G be a simple graph with n vertices, n>2. G has a Hamilton circuit if each vertex has degree greater than or equal to n/2. ❖ Proof: If any two vertices of G are adjacent ,then G has a Hamilton circuit v1 ,v2 ,v3 ,…vn ,v1。 ❖ If G has two vertices u and v that are not adjacent, then d(u)+d(v)≥n. ❖ By the theorem 5.9, G has a Hamilton circuit. ❖ Kn has a Hamilton circuit where n≥3