☆53.2 Hamilton paths (b)
❖5.3.2 Hamilton paths
Definition 20: A Hamilton paths is a path that contains each vertex exactly once. A Hamilton circuit is a circuit that contains each vertex exactly once except for the first vertex, which is also the last
❖ Definition 20: A Hamilton paths is a path that contains each vertex exactly once. A Hamilton circuit is a circuit that contains each vertex exactly once except for the first vertex, which is also the last
g Theorem 5.8: Suppose G(V,E that has a Hamilton circuit, then for each nonempty proper subset s of V(G), the result which o(G S)sS holds, where G-S is the subgraph of g by omitting all vertices of s from V(G). o(G-S)=1,|S b The graph G has not any Hamilton circuit if there is a nonempty purely subgraph s of G-a.d? G so that a(G-s)>s
❖ Theorem 5.8: Suppose G(V,E) that has a Hamilton circuit, then for each nonempty proper subset S of V(G), the result which (GS)≤|S| holds, where G-S is the subgraph of G by omitting all vertices of S from V(G). (G-S)=1，|S|=2 The graph G has not any Hamilton circuit, if there is a nonempty purely subgraph S of G so that (G-S)>|S|
Omit (b, h, i] from V, BO(G-s=4>3=S, The graph has not any Hamilton circuit g
❖ Omit {b,h,i} from V, ❖ (G-S)=4>3=|S|，The graph has not any Hamilton circuit
o If o(G-S)ss for each nonempty proper subset s of g. then g has a hamilton circuit or has not any Hamilton circuit 8 For example: Petersen graph
❖ If (G-S)≤|S| for each nonempty proper subset S of G, then G has a Hamilton circuit or has not any Hamilton circuit. ❖ For example: Petersen graph