块 ■对于阶至少为3的连通图G 1.G没有割点。 →2.对于任意两个顶点弘，v∈V,G含两条无公共内顶点的路。 ■删去v的邻点w,仍存在其它的-v路，与经过w的-v路组成圈。 这样证明存在什么问题？如何解决这个问题？ u 2023/3/20
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 n 删去v的邻点w，仍存在其它的u-v路，与经过w的u-v路组成圈。 这样证明存在什么问题？如何解决这个问题？ 2023/3/20 21 块 u w v
块 ■对于阶至少为3的连通图G 1.G没有割点。 →2.对于任意两个顶点，v∈V,G含两条无公共内顶点的路。 ■删去v的邻点w,仍存在其它的-v路，与经过w的-v路组成圈。 这样证明存在什么问题？如何解决这个问题？ V 2023/3/20
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 n 删去v的邻点w，仍存在其它的u-v路，与经过w的u-v路组成圈。 这样证明存在什么问题？如何解决这个问题？ 2023/3/20 22 块 u w v
块 ■对于阶至少为3的连通图G 1.G没有割点。 →2.对于任意两个顶点弘，v∈V,G含两条无公共内顶点的路。 ■采用数学归纳法，对两个顶点间的距离归纳。 ●当dis(4,v)=1时，为什么成立？ V u 2023/3/20 23
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 n 采用数学归纳法，对两个顶点间的距离归纳。 l 当dist(u, v) = 1时，为什么成立？ 2023/3/20 23 块 u v
块 ■对于阶至少为3的连通图G 1.G没有割点。 →2.对于任意两个顶点，v∈V,G含两条无公共内顶点的路。 ■采用数学归纳法，对两个顶点间的距离归纳。 ●当dis(u,)=1时，为什么成立？ -G没有割点→没有割边→和共圈 u 2023/3/20 24
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 n 采用数学归纳法，对两个顶点间的距离归纳。 l 当dist(u, v) = 1时，为什么成立？ – G没有割点 à 没有割边 à u和v共圈 2023/3/20 24 块 u v
块 ■对于阶至少为3的连通图G 1.G没有割点。 →2.对于任意两个顶点弘，v∈V,G含两条无公共内顶点的路。 ■采用数学归纳法，对两个顶点间的距离归纳。 ●当dis(u,v)=1时，为什么成立？ -G没有割点→没有割边→和v共圈 ●假设ds(u,v)=时成立，则dis(以，v)=k+1时 -dis代L.r)=k今共圈 u W 2023/3/20 25
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 n 采用数学归纳法，对两个顶点间的距离归纳。 l 当dist(u, v) = 1时，为什么成立？ – G没有割点 à 没有割边 à u和v共圈 l 假设dist(u, v) = k时成立，则dist(u, v) = k + 1时 – dist(u, w) = k à 共圈 2023/3/20 25 块 u w P v Q