证明无向图点连通度小于等于边连通度小于等于最小度?

来源:百度知道 编辑:UC知道 时间:2024/05/20 00:18:49
当G连通时先证边连通度小于等于最小度再证点连通度小于等于边连通度。

k(G)≤l(G)≤δ(G)。证明 若 G 不连通, 则k(G)=λ(G)=0,故上式成立。 若 G 连通, 1) 证明λ(G)≤δ(G) 如果 G 是平凡图,则 λ(G)=0≤δ(G),若G是非平凡图,则因每一结点的所有关联边必含一个边割集,故λ(G)≤δ(G) 。
2) 再证 k(G)≤λ(G) (a) 设λ(G)=1,即G有一割边,显然这时k(G)=1,上式成立。 (b) 设λ(G)≥2,则必可删去某λ(G)条边,使G不连通,而删去其中λ(G)-1条边,它仍是连通的,且有一条桥e=(u,v)。对λ(G)-1条边中的每一条边都选取一个不同于u,v的端点,把这些端点删去,则必至少删去λ(G)-1条边。若这样产生的图是不连通的,则k(G)≤λ(G)-1<λ(G),若这样产生的图是连通的,则e仍是桥,此时再删去u或v,就必产生一个不连通图,故 k(G)≤λ(G)。 由 1) 和 2) 得 k(G)≤λ(G)≤δ(G)

写的什么东东???~~~~