定理7(证明(2) 证明:(2)由极大路径得圈:设极大路径 kKn2.(2a)若oV)∈E,则得圈 C=V0v1…Vo.(2b)若()∈E (1sk-1∧(,W)∈E(o+1)∈E) 则,d()+d(w)(o+k1((1)=kn2 (矛盾)于是得圈C=V….WMk1V+1.# 《集合论与图论》第18讲 16
《集合论与图论》第18讲 16 定理7(证明(2)) 证明: (2) 由极大路径得圈: 设极大路径 Γ=v0v1…vk, k≤n-2. (2a) 若(v0,vk)∈E,则得圈 C=v0v1…vkv0. (2b) 若(v0,vk)∉E,则 ∃i( 1≤i≤k-1∧(vi,vk)∈E∧(v0,vi+1)∈E ), 否则, d(v0)+d(vk)≤d(v0)+k-1-(d(v0)-1)=k≤n-2 (矛盾). 于是得圈C=v0…vivkvk-1…vi+1v0. # v0 vk vi vi+1 v0 vk
无向哈密顿图的充分条件 推论:设G是n(23阶无向简单图,若对G 中任意不相邻顶点u与v有 d(u+d(vzn 则G是哈密顿图 证明:由定理7知G连通且有哈密顿通路 I=V1Vn(1)若(vd)∈E,则得哈密顿 回路C=VV1…nV0(2)若(W0E则与 定理7证明(2b)类似,也存在哈密顿回路.# 《集合论与图论》第18讲
《集合论与图论》第18讲 17 无向哈密顿图的充分条件 推论1: 设G是n(≥3)阶无向简单图,若对G 中任意不相邻顶点u与v有 d(u)+d(v)≥n 则G是哈密顿图. 证明: 由定理7知G连通且有哈密顿通路 Γ=v0v1…vn. (1) 若(v0,vn)∈E,则得哈密顿 回路C=v0v1…vnv0. (2) 若(v0,vk)∉E,则与 定理7证明(2b)类似,也存在哈密顿回路. #