Pré-visualização50 páginas

of Fi. If x; y are the ends of a path in F 0i \C0, then also xFiy µ C0. (1) Let e = vw be the new edge in E(F 0i )rE [F ]; this is the only edge of F 0i not lying in Fi. We assume that e 2 xF 0 iy: otherwise we would have xFiy = xF 0iy and nothing to show. It su\u2013ces to show that vFiw µ C0: then (xF 0iy¡ e)[ vFiw is a connected subgraph of Fi \C0 that contains x; y, and hence also xFiy. Let e0 be any edge of vFiw. Since we could replace e0 in F 2 F0 by e and obtain an element of F0 not contain- ing e0, we have e0 2 E0. Thus vFiw µ G0, and hence vFiw µ C0 since v; w 2 xF 0iy µ C0. This proves (1). In order to prove that U = V (C0) is connected in F 0i we show that, for every edge xy 2 C0, the path xF 0i y exists and lies in C 0. As C0 is connected, the union of all these paths will then be a connected spanning subgraph of F 0i [U ]. So let e = xy 2 C0 be given. As e 2 E0, there exist an s 2 N and k-tuples F r = (F r1 ; : : : ; F r k ) for r = 1; : : : ; s such that each F r is obtained from F r¡1 by edge replacement and e 2 E rE [F s ]. Setting 60 3. Connectivity F := F s in (1), we may think of e as a path of length 1 in F 0i \ C0. Successive applications of (1) to F = F s; : : : ; F 0 then give xF 0i y µ C0 as desired. \u2044 Proof of Theorem 3.5.1. We prove the backward implication by(1.5.3) induction on jGj. For jGj = 2 the assertion holds. For the induction step, we now suppose that for every partition P of V there are at least k (jP j¡1) cross-edges, and construct k edge-disjoint spanning trees in G. Pick a k-tuple F 0 = (F 01 ; : : : ; F 0 k ) 2 F . If every F 0i is a tree, we areF 0 done. If not, we have kF 0k = kX i=1 kF 0i k < k (jGj ¡ 1) by Corollary 1.5.3. On the other hand, we have kGk > k (jGj ¡ 1) by assumption: consider the partition of V into single vertices. So there exists an edge e0 2 E r E [F 0 ]. By Lemma 3.5.3, there exists a sete0 U µ V that is connected in every F 0i and contains the ends of e0; inU particular, jU j > 2. Since every partition of the contracted multigraph G=U induces a partition of G with the same cross-edges,3 G=U has at least k (jP j ¡ 1) cross-edges with respect to any partition P . By the induction hypothesis, therefore, G=U has k edge-disjoint spanning trees T1; : : : ; Tk. Replacing in each Ti the vertex vU contracted from U by the spanning tree F 0i \G [U ] of G [U ], we obtain k edge-disjoint spanning trees in G. \u2044 Let us say that subgraphs G1; : : : ; Gk of a graph G partition G if graph partition their edge sets form a partition of E(G). Our spanning tree problem may then be recast as follows: into how many connected spanning subgraphs can we partition a given graph? The excuse for rephrasing our simple tree problem in this more complicated way is that it now has an obvious dual (cf. Theorem 1.5.1): into how few acyclic (spanning) subgraphs can we partition a given graph? Or for given k: which graphs can be partitioned into at most k forests? An obvious necessary condition now is that every set U µ V (G) induces at most k (jU j ¡ 1) edges, no more than jU j ¡ 1 for each forest. Once more, this condition turns out to be su\u2013cient too. And surprising- ly, this can be shown with the help of Lemma 3.5.3, which was designed for the proof of our theorem on edge-disjoint spanning trees: Theorem 3.5.4. (Nash-Williams 1964) A multigraph G = (V;E) can be partitioned into at most k forests if and only if kG [U ]k 6 k (jU j ¡ 1) for every non-empty set U µ V . 3 see Chapter 1.10 on the contraction of multigraphs 3.5 Edge-disjoint spanning trees 61 Proof . The forward implication was shown above. Conversely, we show (1.5.3) that every k-tuple F = (F1; : : : ; Fk) 2 F partitions G, i.e. that E [F ] = E. If not, let e 2 ErE [F ]. By Lemma 3.5.3, there exists a set U µ V that is connected in every Fi and contains the ends of e. Then G [U ] contains jU j ¡ 1 edges from each Fi, and in addition the edge e. Thus kG [U ]k > k (jU j ¡ 1), contrary to our assumption. \u2044 The least number of forests forming a partition of a graph G is called the arboricity of G. By Theorem 3.5.4, the arboricity is a measure for arboricity the maximum local density: a graph has small arboricity if and only if it is \u2018nowhere dense\u2019, i.e. if and only if it has no subgraph H with "(H) large. 3.6 Paths between given pairs of vertices A graph with at least 2k vertices is said to be k-linked if for every 2k dis- k-linked tinct vertices s1; : : : ; sk, t1; : : : ; tk it contains k disjoint paths P1; : : : ; Pk with Pi = si : : : ti for all i. Thus unlike in Menger\u2019s theorem, we are not merely asking for k disjoint paths between two sets of vertices: we insist that each of these paths shall link a specifled pair of endvertices. Clearly, every k-linked graph is k-connected. The converse, however, is far from true: being k-linked is generally a much stronger property than k-connectedness. But still, the two properties are related: our aim in this section is to prove the existence of a function f :N!N such that every f(k)-connected graph is k-linked. As a lemma, we need a result that would otherwise belong in Chap- ter 8: Theorem 3.6.1. (Mader 1967) There is a function h:N!N such that every graph with average degree at least h(r) contains Kr as a topological minor, for every r 2 N. Proof . For r 6 2, the assertion holds with h(r) = 1; we now assume that (1.2.2)(1.3.1) r > 3. We show by induction on m = r; : : : ; ¡ r 2 ¢ that every graph G with average degree d(G) > 2m has a topological minor X with r vertices and m edges; for m = ¡ r 2 ¢ this implies the assertion with h(r) = 2( r 2). If m = r then, by Propositions 1.2.2 and 1.3.1, G contains a cycle of length at least "(G) + 1 > 2r¡1 + 1 > r+ 1, and the assertion follows with X = Cr. Now let r < m 6 ¡ r 2 ¢ , and assume the assertion holds for smaller m. Let G with d(G) > 2m be given; thus, "(G) > 2m¡1. Since G has a component C with "(C) > "(G), we may assume that G is connected. Consider a maximal set U µ V (G) such that U is connected in G and U 62 3. Connectivity "(G=U) > 2m¡1; such a set U exists, because G itself has the form G=U with jU j = 1. Since G is connected, we have N(U) 6= ;. Let H := G [N(U) ]. If H has a vertex v of degree dH(v) < 2m¡1, weH may add it to U and obtain a contradiction to the maximality of U : when we contract the edge vvU in G=U , we lose one vertex and dH(v) + 1 6 2m¡1 edges, so " will still be at least 2m¡1. Therefore d(H) > \u2013(H) > 2m¡1. By the induction hypothesis, H contains a TY with jY j = r and kY k = m¡ 1. Let x; y be two branch vertices of this TY that are non-adjacent in Y . Since x and y lie in N(U) and U is connected in G, G contains an x{y path whose inner vertices lie in U . Adding this path to the TY , we obtain the desired TX. \u2044 How can Theorem 3.6.1 help with our aim to show that high con- nectivity will make a graph k-linked? Since high connectivity forces the average degree up (even the minimum degree), we may assume by the theorem that our graph contains a subdivision K of a large complete graph. Our plan now is to use Menger\u2019s theorem to link the given ver- tices si and ti disjointly to branch vertices of K, and then to join up the correct pairs of those branch vertices inside K. Theorem 3.6.2. (Jung 1970; Larman & Mani 1970) There is a function f :N! N such that every f(k)-connected graph is k-linked, for all k 2 N. Proof . We prove the assertion for f(k) = h(3k) + 2k, where h is a(3.3.1) function as in Theorem 3.6.1. Let G be an f(k)-connected graph. ThenG d(G) > \u2013(G) > \u2022(G) > h(3k); choose K = TK3k µ G as in TheoremK 3.6.1, and let U denote its set of branch vertices.U For the proof that G is k-linked, let distinct vertices s1; : : : ; sk andsi; ti t1; : : : ; tk of G be given. By deflnition of f(k), we have \u2022(G) > 2k. Hence by Menger\u2019s theorem