Pré-visualização50 páginas

replace x or y by ve; this cycle, too, will be denoted by C=e. Thus, as long as C is not a fundamental triangle, C=e will always denote a unique cycle in G0. Note, however, that in the C=e case of e =2 C the edge set of C=e when viewed as a subset of E(G) need not coincide with E(C), or even be a cycle at all; an example is shown in Figure 3.2.3. e0 e0 C=e ve C e00 e 00 E(C=e) µ G x y x y u w u w u w Fig. 3.2.3. One of the four possibilities for E(C=e) when e =2 C Let us refer to the non-separating induced cycles in G or G0 as basic basic cycles cycles. An element of C(G) will be called good if it is a linear combination good of basic cycles in G; we thus want to show that every element of C(G) is good. The basic idea of our proof is to contract a given cycle C 2 C(G) to C=e, generate C=e in C(G0) by induction, and try to lift the generators back to basic cycles in G that generate C. We start by proving three auxiliary facts. Every fundamental triangle is a basic cycle in G. (1) 48 3. Connectivity A fundamental triangle, wxyw say, is clearly induced in G. If it sepa- rated G, then f ve; w g would separate G0, which contradicts the choice of e. This proves (1). If C µ G is an induced cycle but not a fundamental trian- gle, then C+C=e+D 2 f ;; feg g for some good D 2 C(G). (2) The gist of (2) is that, in terms of \u2018generatability\u2019, C and C=e difier only a little: after the addition of a permissible error term D, at most in the edge e. In which other edges, then, can C and C=e difier? Clearly at most in the two edges eu = uve and ew = vew incident with ve in C=e; cf. Fig. 3.2.3. But these difierences between the edge sets of C=e and C are levelled out precisely by adding the corresponding fundamental triangles uxy and xyw (which are basic by (1)). Indeed, let Du denote the triangle uxy if eu =2 C and ; otherwise, and let Dw denote xyw if ew =2 C and ; otherwise. Then D := Du +Dw satisfles (2) as desired. Next, we show how to lift basic cycles of G0 back to G: For every basic cycle C 0 µ G0 there exists a basic cycle C = C(C 0) µ G with C=e = C 0. (3) If ve =2 C 0, then (3) is satisfled with C := C 0. So we assume that ve 2 C 0. Let u and w be the two neighbours of ve on C 0, and let P be the u{wu;w path in C 0 avoiding ve (Fig. 3.2.4). Then P µ G.P x y u w P Fig. 3.2.4. The search for a basic cycle C with C=e = C0 We flrst assume that fux; uy; wx;wy g µ E(G), and consider (as candidates for C) the cycles Cx := uPwxu and Cy := uPwyu. Both areCx; Cy induced cycles in G (because C 0 is induced in G0), and clearly Cx=e = Cy=e = C 0. Moreover, neither of these cycles separates two vertices of G¡ (V (P ) [ fx; y g) in G, since C 0 does not separate such vertices in G0. Thus, if Cx (say) is a separating cycle in G, then one of the components of G¡ Cx consists just of y. Likewise, if Cy separates G then one of the arising components contains only x. However, this cannot happen for both Cx and Cy at once: otherwise NG(fx; y g) µ V (P ) and hence NG(fx; y g) = fu;w g (since C 0 has no chord), which contradicts \u2022(G) > 3. Hence, at least one of Cx, Cy is a basic cycle in G. 3.2 The structure of 3-connected graphs 49 It remains to consider the case that fux; uy; wx;wy g 6µ E(G), say ux =2 E(G). Then, as above, either uPwyu or uPwxyu is a basic cycle in G, according as wy is an edge of G or not. This completes the proof of (3). We now come to the main part of our proof, the proof that every C 2 C(G) is good. By Proposition 1.9.1 we may assume that C is an C induced cycle in G. By (1) we may further assume that C is not a fundamental triangle; so C=e is a cycle. Our aim is to argue as follows. By (2), C difiers from C=e at most by some good error term D (and possibly in e); by (3), the basic cycles C 0i of G 0 that sum to C=e by induction can be contracted from basic cycles of G, which likewise difier from the C 0i only by a good error term Di (and possibly in e); hence these basic cycles of G and all the error terms together sum to C|except that the edge e will need some special attention. By the induction hypothesis, C=e has a representation C=e = C 01 + : : :+C 0 k C 0 1; : : : ; C 0 k in C(G0), where every C 0i is a basic cycle in G0. For each i, we obtain from (3) a basic cycle C(C 0i) µ G with C(C 0i)=e = C 0i (in particular, C(C 0i) is not a fundamental triangle), and from (2) some good Di 2 C(G) such that C(C 0i) +C 0 i +Di 2 f ;; feg g : (4) We let Ci := C(C 0i) +Di ; C1; : : : ; Ck then Ci is good, and by (4) it difiers from C 0i at most in e. Again by (2), we have C +C=e+D 2 f ;; feg g for some good D 2 C(G), i.e. C +D difiers from C=e at most in e. But D then C+D+C1 + : : :+Ck difiers from C=e+C 01 + : : :+C 0 k = ; at most in e, that is, C +D+C1 + : : :+Ck 2 f ;; feg g : Since C +D+C1 + : : :+Ck 2 C(G) but feg =2 C(G), this means that in fact C +D+C1 + : : :+Ck = ; ; so C = D+C1 + : : :+Ck is good. \u2044 50 3. Connectivity 3.3 Menger\u2019s theorem The following theorem is one of the cornerstones of graph theory. Theorem 3.3.1. (Menger 1927) Let G = (V;E) be a graph and A;B µ V . Then the minimum number [ 3.6.2 ] [ 8.1.2 ] [ 12.3.9 ] [ 12.4.4 ] [ 12.4.5 ] of vertices separating A from B in G is equal to the maximum number of disjoint A{B paths in G. We ofier three proofs. WheneverG;A;B are given as in the theorem, we denote by k = k (G;A;B) the minimum number of vertices separatingk A from B in G. Clearly, G cannot contain more than k disjoint A{B paths; our task will be to show that k such paths exist. First proof. We prove the following stronger statement: If P is any set of fewer than k disjoint A{B paths in G then there is a set Q of jPj+ 1 disjoint A{B paths whose set of ends includes the set of ends of the paths in P. Keeping G and A flxed, we let B vary and apply induction on jG¡Bj. Let R be an A{B path that avoids the (fewer than k) vertices of B that lie on a path in P. If R avoids all the paths in P, then Q := P [ fR g is as desired. (This will happen for jG¡Bj = 0 when all A{B paths are trivial.) If not, let x be the last vertex of R that lies on some P 2 P (Fig. 3.3.1). Put B0 := B [V (xP [xR) and P 0 := ¡P r fP g¢[fPx g. Then jP 0j = jPj and k(G;A;B0) > k(G;A;B), so by the induction hypothesis there is a set Q0 of jPj+ 1 disjoint A{B0 paths whose ends include those of the paths in P 0. Then Q0 contains a path Q ending in x, and a unique path Q0 whose last vertex y is not among the last vertices of the paths in P 0. If y =2 xP , we let Q be obtained from Q0 by adding xP to Q, and adding yR to Q0 if y =2 B. Otherwise y 2 \u201dxP , and we let Q be obtained from Q0 by adding xR to Q and adding yP to Q0. \u2044 A B R P x Px Rx P Fig. 3.3.1. Paths in the flrst proof of Menger\u2019s theorem 3.3 Menger\u2019s theorem 51 Second proof. We show by induction on jGj+ kGk that G contains k disjoint A{B paths. For all G;A;B with k 2 f 0; 1 g this is true. For the induction step let G;A;B with k > 2 be given, and assume that the assertion holds for graphs with fewer vertices or edges. If there is a vertex x 2 A\B, then G¡x contains k¡1 disjoint A{B paths by the induction hypothesis. (Why?) Together with the trivial path fx g, these form the desired paths in G. We shall therefore assume that A\B = ; : (1) We flrst construct the desired paths for the case that A and B are separated by a set X µ V with jXj = k and X 6= A;B. Let CA be X the union of all the components of G¡X meeting A; note that CA 6= ;, since jAj > k = jXj but A 6= X. The subgraph CB deflned likewise is not CA; CB empty either, and CA\CB = ;. Let us write GA := G [V (CA)[X ] and GB := G [V (CB) [X ]. Since every A{B path in G contains an A{X GA; GB path in GA, we cannot separate A from X in GA by fewer than k vertices. Thus, by the induction hypothesis,