定理43.2若G是H图,则对V(G)的每个非空真子集S,均有: 连通分支数W(G-S)≤|S|e 证明:设C是G的H圈,则对VG)的每个非空真子集S,均有 由于C-S是G-S的生成子图,故W(G-S)≤WC-S)≤|S 证毕 利用定理432可判断下面(1)中的图不是H图。事实上,令S={u,V,w},则 H(G-S)=4>|S| 但无法用该定理给出的必要条件来判断(2)中的 Petersen图不是H图。 (1) 、充分条件 (1)度型条件 定理433 Dirac,1952)若G是简单图,且v≥3,d≥一,则G是 Hamilton图 证明用反证法:假定定理不真。令 A={G|G的顶点数为v≥3,d≥,且G是非 Hamilton图}。 2 从A中取出边最多的一个,记为G。因v≥3,故不是完全图(否则G是 Hamilton图)。设 u和v是G的不相邻顶点。由G的选择,G+w是 Hamilton图。因G是非 Hamilton图,故 G+m的H圈必经过e=。于是G中存在以u为起点v为终点的 Hamilton路vv2…",。 这里v1=a,v=",令 S={v|a∈E}和T={v|vv∈E} Vi vi+l 由于 V E SUT,故S∪Tkv,并且S∩TF=0(因为若彐v,∈S∩T,则G将包含H 圈v1V2…vv,1…Vv1,矛盾)。 V1v2v3…vv+1…V1vr 故d(n)+d()=S|+|THSU7|+|S∩Tkv,这与d≥的前提矛盾。证毕9 定理 4.3.2 若 G 是 H 图，则对 V(G)的每个非空真子集 S，均有： 连通分支数 W(G－S) ≤ | S |。 证明：设 C 是 G 的 H 圈，则对 V(G)的每个非空真子集 S，均有 W(C－S) ≤ | S |. 由于 C－S 是 G－S 的生成子图，故 W(G－S)≤W(C－S)≤ | S |. 证毕。 利用定理 4.3.2 可判断下面(1)中的图不是 H 图。事实上，令 S={u, v, w}，则 W(G－S) = 4 > | S |。 但无法用该定理给出的必要条件来判断(2)中的 Petersen 图不是 H 图。 二、充分条件 （1）度型条件 定理 4.3.3(Dirac, 1952) 若 G 是简单图，且ν ≥ 3， 2 ν δ ≥ ，则 G 是 Hamilton 图。 证明 用反证法：假定定理不真。令 A = {G |G 的顶点数为ν ≥ 3， 2 ν δ ≥ ，且 G 是非 Hamilton 图}。 从 A 中取出边最多的一个，记为 G。因ν ≥ 3，故不是完全图（否则 G 是 Hamilton 图）。设 u 和 v 是 G 的不相邻顶点。由 G 的选择，G＋uv 是 Hamilton 图。因 G 是非 Hamilton 图，故 G＋uv 的 H 圈必经过 e = uv。于是 G 中存在以 u 为起点 v 为终点的 Hamilton 路 ν v v "v 1 2 。 这里v = u 1 ，v = v ν ，令 { | } S = vi uvi+1 ∈ E 和T {v | v v E} = i i ∈ 。 由于vν ∉ S ∪T ，故| S ∪T |<ν ，并且| S ∩T |= 0 （因为若∃vi ∈ S ∩T ，则 G 将包含 H 圈 1 2 1 1 1 v v v v v v v " i ν ν − " i+ ，矛盾）。 故d(u) + d(v) =| S | + | T |=| S ∪T | + | S ∩T |<ν ，这与 2 ν δ ≥ 的前提矛盾。证毕。 u v w （1） （2） v1 v2 v3… vi vi+1… vv-1 vv u v v1 v2 v3… vi vj … vv-1 vv u v vi+1