Pré-visualização50 páginas

GA contains k disjoint A{X paths (Fig. 3.3.2). In the same way, there are k disjoint X{B paths in GB . As jXj = k, we can put these paths together to form k disjoint A{B paths. GA GB X A A B Fig. 3.3.2. Disjoint A{X paths in GA For the general case, let P be any A{B path in G. By (1), P has an edge ab with a =2 B and b =2 A. Let Y be a set of as few vertices as ab possible separating A from B in G¡ab (Fig. 3.3.3). Then Ya := Y [f a g Y and Yb := Y [f b g both separate A from B in G, and by deflnition of k Ya; Yb we have jYaj; jYbj > k : If equality holds here, we may assume by the case already treated that fYa; Yb g µ fA;B g, so fYa; Yb g = fA;B g since a =2 B and b =2 A. Thus, Y = A\B. Since jY j > k¡ 1 > 1, this contradicts (1). We therefore have either jYaj > k or jYbj > k, and hence jY j > k. By the induction hypothesis, then, there are k disjoint A{B paths even in G¡ ab µ G. \u2044 52 3. Connectivity A B Y P a b Fig. 3.3.3. Separating A from B in G¡ ab Applied to a bipartite graph, Menger\u2019s theorem specializes to the assertion of Ko\u2dcnig\u2019s theorem (2.1.1). For our third proof, we now adapt the alternating path proof of Ko\u2dcnig\u2019s theorem to the more general set- up of Theorem 3.3.1. Let again G;A;B be given, and let P be a set ofP disjoint A{B paths in G. We write V [P ] := [ fV (P ) j P 2 P g E [P ] := [ fE(P ) j P 2 P g : A walk W = x0e0x1e1 : : : en¡1xn in G with ei 6= ej for i 6= j is said to be alternating with respect to P if the following three conditions are satisfled for all i < n (Fig. 3.3.4):alternatingwalk (i) if ei = e 2 E [P ], then W traverses the edge e backwards, i.e. xi+1 2 P\u201dxi for some P 2 P; (ii) if xi = xj with i 6= j, then xi 2 V [P ]; (iii) if xi 2 V [P ], then f ei¡1; ei g\E [P ] 6= ;.2 Px0 xn A B W Fig. 3.3.4. An alternating walk from A to B 2 For i = 0 we let f ei¡1; ei g := f e0 g. 3.3 Menger\u2019s theorem 53 Let us consider a walk W = x0e0x1e1 : : : en¡1xn from Ar V [P ] W;xi; ei to BrV [P ], alternating with respect to P. By (ii), any vertex outside V [P ] occurs at most once on W . Since the edges ei of W are all distinct, (iii) implies that any vertex in V [P ] occurs at most twice on W . This can happen in two ways: if xi = xj with 0 < i < j < n, say, then either ei¡1; ej 2 E [P ] and ei; ej¡1 =2 E [P ] or ei; ej¡1 2 E [P ] and ei¡1; ej =2 E [P ] : Lemma 3.3.2. If such a walk W exists, then G contains jPj+1 disjoint A{B paths. Proof . Let H be the graph on V [P ][fx0; : : : ; xn g whose edge set is the symmetric difierence of E [P ] with f e0; : : : ; en¡1 g. In H, the ends of the paths in P and of W have degree 1 (or 0, if the path or W is trivial), and all other vertices have degree 0 or 2. For each of the jPj+ 1 vertices a 2 (A\ V [P ])[ fx0 g, therefore, the component of H containing a is a path, P = v0 : : : vk say, which starts in a and ends in A or B. Using P conditions (i) and (iii), one easily shows by induction on i = 0; : : : ; k¡ 1 that P traverses each of its edges e = vivi+1 in the forward direction with respect to P or W . (Formally: if e 2 P 0 with P 0 2 P, then vi 2 P 0\u201dvi+1; if e = ej 2 W , then vi = xj and vi+1 = xj+1.) Hence, P ends in B. As we have jPj+ 1 disjoint such paths P , this completes the proof. \u2044 Third proof of Menger\u2019s theorem. Let P be a set of as many disjoint P A{B paths in G as possible. Unless otherwise stated, all alternating walks considered are alternating with respect to P. We set A1 := A\V [P ] and A2 := ArA1 ; A1; A2 and B1 := B \V [P ] and B2 := BrB1 : B1; B2 For every path P 2 P, let xP be the last vertex of P that lies on xP some alternating walk starting in A2; if no such vertex exists, let xP be the flrst vertex of P . Clearly, the set X := fxP j P 2 P g X has cardinality jPj; it thus su\u2013ces to show that X separates A from B. Let Q be any A{B path in G; we show that Q meets X. Suppose Q not. By the maximality of P, the path Q meets V [P ]. Since the A{ V [P ] path in Q is trivially an alternating walk, Q also meets the vertex set V [P 0 ] of P 0 := fPxP j P 2 P g ; P 0 54 3. Connectivity let y be the last vertex of Q in V [P 0 ], let P be the path in P containing y,y; P and let x := xP . Finally, let W be an alternating walk from A2 to x,x;W as in the deflnition of xP . By assumption, Q avoids X and hence x, so y 2 P\u201dx, and W [ xPyQ is a walk from A2 to B (Fig. 3.3.5). If this walk is alternating and ends in B2, we are home: then G contains jPj+ 1 disjoint A{B paths by Lemma 3.3.2, contrary to the maximality of P. P Q W y x z Qy Fig. 3.3.5. Alternating walks in the third proof of Menger\u2019s the- orem How could W [ xPyQ fail to be an alternating walk? For a start, W might already use an edge of xPy. But if x0 is the flrst vertex of W on xP\u201dy, then W 0 := Wx0Py is an alternating walk from A2 to y. (Byx0;W 0 Wx0 we mean the initial segment of W ending at the flrst occurrence of x0 on W ; from there onwards, W 0 follows P back to y.) Even our new walk W 0yQ need not yet be alternating: W 0 might still meet \u201dyQ. By deflnition of P 0 and W , however, and the choice of y on Q, we have V (W 0)\V [P ] µ V [P 0 ] and V (\u201dyQ)\V [P 0 ] = ; : Thus, W 0 and \u201dyQ can meet only outside P. If W 0 does indeed meet \u201dyQ, let z be the flrst vertex of W 0 on \u201dyQ. Asz z lies outside V [P ], it occurs only once on W 0 (condition (ii)), and we let W 00 := W 0zQ. On the other hand if W 0\\u201dyQ = ;, we set W 00 := W 0[yQ.W 00 In both cases, W 00 is alternating with respect to P 0, becauseW 0 is and \u201dyQ avoids V [P 0 ]. (Note that W 00 satisfles condition (iii) at y in the second case, while in the flrst case (iii) is not applicable to z.) By deflnition of P 0, therefore, W 00 avoids V [P ]r V [P 0 ]; in particular, V (\u201dyQ)\ V [P ] = ;. Thus W 00 is also alternating with respect to P, and it ends in B2. (Note that y cannot be the last vertex of W 00, since y 2 P\u201dx and hence y =2 B.) Furthermore, W 00 starts in A2, because W does. We may therefore use W 00 with Lemma 3.3.2 to obtain the desired contradiction to the maximality of P. \u2044 3.3 Menger\u2019s theorem 55 A set of a{B paths is called an a{B fan if any two of the paths have fan only a in common. Corollary 3.3.3. For B µ V and a 2 V rB, the minimum number of [ 10.1.2 ] vertices 6= a separating a from B in G is equal to the maximum number of paths forming an a{B fan in G. Proof . Apply Theorem 3.3.1 with A := N(a). \u2044 Corollary 3.3.4. Let a and b be two distinct vertices of G. (i) If ab =2 E, then the minimum number of vertices 6= a; b separating a from b in G is equal to the maximum number of independent a{b paths in G. (ii) The minimum number of edges separating a from b in G is equal to the maximum number of edge-disjoint a{b paths in G. Proof . (i) Apply Theorem 3.3.1 with A := N(a) and B := N(b). (ii) Apply Theorem 3.3.1 to the line graph of G, with A := E(a) and B := E(b). \u2044 Theorem 3.3.5. (Global Version of Menger\u2019s Theorem) [ 4.2.10 ] [ 6.6.1 ] [ 9.4.2 ](i) A graph is k-connected if and only if it contains k independent paths between any two vertices. (ii) A graph is k-edge-connected if and only if it contains k edge- disjoint paths between any two vertices. Proof . (i) If a graph G contains k independent paths between any two vertices, then jGj > k and G cannot be separated by fewer than k ver- tices; thus, G is k-connected. Conversely, suppose that G is k-connected (and, in particular, has more than k vertices) but contains vertices a; b not linked by k indepen- a; b dent paths. By Corollary 3.3.4 (i), a and b are adjacent; let G0 := G¡ab. G0 Then G0 contains at most k ¡ 2 independent a{b paths. By Corollary 3.3.4 (i), we can separate a and b in G0 by a set X of at most k ¡ 2 X vertices. As jGj > k, there is at least one further vertex v =2 X [f a; b g v in G. Now X separates v in G0 from either a or