定理2.22对具有D个顶点E条边的连通图9,有(G)≤ 证明:因2E=∑d()≥b,故δ≤,由定理221,k≤δ≤2。由于K是整数, lE/(G) 因此K≤ 证毕 定理23设G是一个简单图,k是一个自然数,若(G)≥+k-2 ,则G是k连通的。 证明:用反证法。假如G不是k连通的,则G的连通度K<k,即存在G的点割集S,使 得|Skk,且G-S不连通。因G-S有U-|S|个顶点,且至少有两个连通分支,故必有G-S 的某个连通分支G含有不超过/S 个顶点。注意到G’中任一个顶点只可能与G内的点 2 及S中的点相邻,因而其在G中的顶点度=15|-1+1S=2+5S12.结合|Skk 这意味着6(G)≤+1S-2<”+k-2,与定理条件矛盾。证毕 推论221设G是一个简单图,若(G)≥,则G是连通的 定理224设G是一个直径为2的简单图,则x(G)=o(G)。 证明:设S是G的一个最小边割集,则G-S有多于一个连通分支,取其中顶点数最少的一 个记为G1,GS的其余部分记为G2 如果G1中存在顶点a,它在G中不与G2的顶点相邻,则对,由d(l,v)=2知,在G 中v有属于G1的邻点。由此可知,在G中来看,要么G1中每个点都在G2中有邻点,要么 G2中每个点都在G1中有邻点。在前一种情况下,|SpU(G1),在后一种情况下, SEU(G2)。总之,K'=Smin{b(G1,D(G2)}=D(G1)。 (1) 对va∈G1,用d1(u)和d1()分别表示在G中u与G1和G2连的边数。则 (G)≤d0(u)=d1(l)+d2(u)≤D(G1)-1+d2(l)。 根据定理22.1, K'≤(G)≤U(G1)-1+d2(un) 结合(1)式可得d2()≥1。任取l0∈V(G1),由于 k'=SF∑d2()=∑d2(l)+d2(l)≥U(G)-1+d2(a), 结合(2)式得5 定理 2.2.2 对具有υ 个顶点ε 条边的连通图 G，有 2 ( ) G ε κ ν ⎢ ⎥ ≤ ⎢ ⎥ ⎣ ⎦ 。 证明：因 ( ) 2 () vVG ε d v δυ ∈ = ≥ ∑ ，故 2ε δ υ ≤ ，由定理 2.2.1， 2ε κ δ υ ≤ ≤ 。由于κ 是整数， 因此 2ε κ ν ⎢ ⎥ ≤ ⎢ ⎥ ⎣ ⎦ 。证毕。 定理 2.2.3 设 G 是一个简单图，k 是一个自然数，若 2 ( ) 2 k G υ δ + − ≥ ，则 G 是 k 连通的。 证明：用反证法。假如 G 不是 k 连通的，则 G 的连通度κ < k ，即存在 G 的点割集 S，使 得| | S k < ，且 G−S 不连通。因 G −S 有υ− |S|个顶点，且至少有两个连通分支，故必有 G−S 的某个连通分支G′含有不超过 |S| 2 υ− 个顶点。注意到G′中任一个顶点只可能与G′内的点 及 S 中的点相邻，因而其在 G 中的顶点度 | | |S| 2 1| | 2 2 S S υ− υ+ − ≤ −+ = 。结合| | S k < ， 这意味着δ (G) ≤ | |2 2 2 2 υ+ S k − +− υ < ，与定理条件矛盾。证毕。 推论 2.2.1 设 G 是一个简单图，若 1 ( ) 2 G υ δ − ≥ ，则 G 是连通的。 定理 2.2.4 设 G 是一个直径为 2 的简单图，则κ′(G) (G) = δ 。 证明：设 S 是 G 的一个最小边割集，则 G−S 有多于一个连通分支，取其中顶点数最少的一 个记为 G1，G−S 的其余部分记为 G2。 如果 G1 中存在顶点 u，它在 G 中不与 G2 的顶点相邻，则对，由 (,) 2 G d uv = 知，在 G 中 v 有属于 G1 的邻点。由此可知，在 G 中来看，要么 G1 中每个点都在 G2 中有邻点，要么 G2 中每个点都在 G1 中有邻点。在前一种情况下， 1 | S | (G ) ≥ υ ，在后一种情况下， 2 | S | (G ) ≥ υ 。总之， 12 1 κ υυ υ ′ =≥ = | S | min{ (G ), (G )} (G ) 。 （1） 对 1 ∀ ∈u G ，用 1 d u( ) 和 1 d u( ) 分别表示在 G 中 u 与 G1和 G2 连的边数。则 12 1 2 ( ) () () () ( ) 1 () G d u du du G du G δ ≤ = + ≤ −+ υ 。 根据定理 2.2.1， κ δ ′ ≤ ≤ (G) 1 2 υ( ) 1 () G du − + 。 （2） 结合（1）式可得 2 d u() 1 ≥ 。 任取 0 1 u VG ∈ ( ) ，由于 1 10 2 2 20 1 20 | | () () ( ) ( ) 1 ( ) uG uG u κ υ S du du du G du ∈ ∈− ′ = = = + ≥ −+ ∑ ∑ ， 结合（2）式得