121.The BasicsIf JG| > 1 and G-F is connected for every set F E of fewerl-edgthan I edges, then G is called l-edge-connected. The greatest integer connectedsuch that G is l-edge-connected is the edge-connectivity A(G) of G. Inedgeconnectivity particular, we have (G) = O if G is disconnected.入(G)GFig. 1.4.3. The octahedron G (left) with x(G) = 入(G) = 4and a graph H with k(H) = 2 but (H) = 4Proposition 1.4.2. If G is non-trivial then k(G) ≤ ^(G) ≤ (G)Proof. The second inequality follows from the fact that all the edgesincident with a fixed vertex separate G. To prove the first, let F be anyminimal subset of E such that G - F is disconnected. We show thatk(G) ≤[F}.Suppose first that G has a vertex u that is not incident with an edgein F. Let C be the component of G - F containing v. Then the verticesof C that are incident with an edge in F separate u from G- C. Sinceno edge in F has both ends in C (by the minimality of F), there are atmost [F| such vertices, giving k(G) ≤ [F as desired.Suppose now that every vertex is incident with an edge in F. Let ybe any vertex, and let C be the component of G-F containing u. Thenw of v with ww F lie in C and are incident with distincttheneighboedges in F, giving dc(u) ≤ [F]. As Nc(u) separates u from all the othervertices in G, this yields k(G) < [Funless there are no other vertices.i.e. unless (uN(u) = V. But v was an arbitrary vertex. So we may口assume that G is complete, giving r(G) = ^(G) = [G| - 1.By Proposition 1.4.2, high connectivity requires a large minimumdegree. Conversely, large minimum degree does not ensure high connec-tivity, not even high edge-connectivity (examples?).It does, however,imply the existence of a highly connected subgraph:[72]Theorem 1.4.3. (Mader 1972)Let 0 + k e N. Every graph G with d(G) ≥ 4k has a (k+ 1)-connectedsubgraph H such that e(H) > (G) -k12 1. The Basics If |G| > 1 and G − F is connected for every set F ⊆ E of fewer than  edges, then G is called -edge-connected. The greatest integer  -edge￾connected such that G is -edge-connected is the edge-connectivity λ(G) of G. In particular, we have λ(G) = 0 if G is disconnected. edge￾connectivity λ(G) G H Fig. 1.4.3. The octahedron G (left) with κ(G) = λ(G) = 4, and a graph H with κ(H)=2 but λ(H)=4 Proposition 1.4.2. If G is non-trivial then κ(G) λ(G) δ(G). Proof . The second inequality follows from the fact that all the edges incident with a fixed vertex separate G. To prove the first, let F be any minimal subset of E such that G − F is disconnected. We show that κ(G) |F|. Suppose first that G has a vertex v that is not incident with an edge in F. Let C be the component of G−F containing v. Then the vertices of C that are incident with an edge in F separate v from G − C. Since no edge in F has both ends in C (by the minimality of F), there are at most |F| such vertices, giving κ(G) |F| as desired. Suppose now that every vertex is incident with an edge in F. Let v be any vertex, and let C be the component of G−F containing v. Then the neighbours w of v with vw /∈ F lie in C and are incident with distinct edges in F, giving dG(v) |F|. As NG(v) separates v from all the other vertices in G, this yields κ(G) |F|—unless there are no other vertices, i.e. unless { v } ∪ N(v) = V . But v was an arbitrary vertex. So we may assume that G is complete, giving κ(G) = λ(G) = |G| − 1.
By Proposition 1.4.2, high connectivity requires a large minimum degree. Conversely, large minimum degree does not ensure high connec￾tivity, not even high edge-connectivity (examples?). It does, however, imply the existence of a highly connected subgraph: Theorem 1.4.3. (Mader 1972) [ 7.2.1 ] [ 11.2.3 ] Let 0 = k ∈ N. Every graph G with d(G) 4k has a (k + 1)-connected subgraph H such that ε(H) > ε(G) − k.