Pré-visualização50 páginas

Proof . Let V := fVx j x 2 V (H) g be the set of branch sets in G(3.3.1) V; Vx corresponding to the vertices of H. For our proof that G is (k; dk=2e)- linked, let k distinct vertices v1; : : : ; vk 2 G be given. Let us call av1; : : : ; vk sequence P1; : : : ; Pk of disjoint paths in G a linkage if the Pi each startlinkage in vi and end in pairwise distinct sets V 2 V; the paths Pi themselves will be called links. Since our assumptions about H imply that jHj > k, andlink G is k-connected, such linkages exist: just pick k vertices from pairwise distinct sets V 2 V, and link them disjointly to f v1; : : : ; vk g by Menger\u2019s theorem. Now let P = (P1; : : : ; Pk) be a linkage whose total number of edgesP outside S V 2V G [V ] is as small as possible. Thus, if f(P ) denotes theP1; : : : ; Pk number of edges of P not lying in any G [Vx ], we choose P so as tof(P ) minimize Pk i=1 f(Pi). Then for every V 2 V that meets a path Pi 2 P there exists one such path that ends in V : if not, we could terminate Pi in V and reduce f(Pi). Thus, exactly k of the branch sets of H meet a link. Let us divide these sets into two classes: U := fV 2 V j V meets exactly one link g W := fV 2 V j V meets more than one link g : U W Since H is dense and each U 2 U meets only one link, it will be easy to show that the starting vertices vi of those links form a linked set in G. Hence, our aim is to show that jUj > dk=2e, i.e. that U is no smaller than W. (Recall that jUj+ jWj = k.) To this end, we flrst prove the following: Every V 2 W is met by some link which leaves V again and next meets a set from U (where it ends). (1) Suppose Vx 2 W is a counterexample to (1). Sincex 2\u2013(H) > jHj+ 32k > \u2013(H) + 32k ; we have \u2013(H) > 32k. As jU [Wj = k, this implies that x has a neighbour y in H with Vy 2 V r (U [W); let wxwy be an edge of G with wx 2 Vx and wy 2 Vy. Let Q = w : : : wxwy be a path in G [Vx [fwy g ] of whose vertices only w lies on any link, say on Pi (Fig. 8.1.2). Replacing Pi inPi P by P 0i := PiwQ then yields another linkage.P 0i If Pi is not the link ending in Vx, then f(P 0i ) 6 f(Pi). The choice of P then implies that f(P 0i ) = f(Pi), i.e. that Pi ends in the branch set W it enters immediately after Vx. Since Vx is a counterexample to (1) we have W =2 U , i.e. W 2 W. Let P 6= Pi be another link meeting W . Then P does not end in W (because Pi ends there); let P 0 µ P be the (minimal) initial segment of P that ends in W . If we now replace Pi and P by P 0i and P 0 in P, we obtain a linkage contradicting the choice of P. 8.1 Topological minors 173 H Vx 2W wx P 0 W 2W Vy 2 V r (U [W) P Pi w Pi wy P 0i Fig. 8.1.2. If Pi does not end in Vx, we replace Pi and P by P 0 i and P 0 We now assume that Pi does end in Vx; then f(P 0i ) = f(Pi) + 1. As Vx 2 W, there exists a link Pj that meets Vx and leaves it again; let P 0j be the initial segment of Pj ending in Vx (Fig 8.1.3). Then f(P 0 j) 6 f(Pj)¡ 1. In fact, since replacing Pi and Pj with P 0i and P 0j in P yields another linkage, the choice of P implies that f(P 0j) = f(Pj)¡ 1, so Pj ends in the branch set W it enters immediately after Vx. Then W 2 W as before, so we may deflne P and P 0 as before. Replacing Pi, Pj and P by P 0i , P 0 j and P 0 in P, we flnally obtain a linkage that contradicts the choice of P. This completes the proof of (1). Pi w H wy P 0 W 2W Vy 2 V r (U [W) P 0j Pj P Pi Vx 2W P 0i Fig. 8.1.3. If Pi ends in Vx, we replace Pi; Pj ; P by P 0 i ; P 0 j ; P 0 With the help of (1) we may deflne an injection W!U as follows: given W 2 W, choose a link that passes through W and next meets a set U 2 U , and map W 7! U . (This is indeed an injection, because difierent links end in difierent branch sets.) Thus jUj > jWj, and hence jUj > dk=2e. Let us assume the enumeration of v1; : : : ; vk to be such that the flrst u := jUj of the links P1; : : : ; Pk end in sets from U . Since 2\u2013(H) > u 174 8. Substructures in Sparse Graphs jHj+ 32k, we can flnd for any two sets Vx; Vy 2 U at least 32k sets Vz such that xz; yz 2 E(H). At least k=2 of these sets Vz do not lie in U [W. Thus whenever U1; : : : ; U2h are distinct sets in U (so h 6 u=2 6 k=2), we may flnd inductively h distinct sets V i 2 Vr (U [W) (i = 1; : : : ; h) such that V i is joined in G to both U2i¡1 and U2i. For each i, any vertex of U2i¡1 can be linked by a path through V i to any desired vertex of U2i, and these paths will be disjoint for difierent i. Joining up the appropriate pairs of paths from P in this way, we see that the set f v1; : : : ; vu g is linked in G, and the lemma is proved. \u2044 Lemma 8.1.3. Let k > 6 be an integer. Then every graph G with "(G) > k has a minor H such that 2\u2013(H) > jHj+ 16k. Proof . We begin by choosing a (4-)minimal minor G0 of G withG0 "(G0) > k. The minimality of G0 implies that \u2013(G0) > k and "(G0) = k (otherwise we could delete a vertex or an edge of G0), and hence k+ 1 6 \u2013(G0) 6 d(G0) = 2k : Let x0 2 G0 be a vertex of minimum degree.x0 If k is odd, let m := (k+ 1)=2 and G1 := G0 [ fx0 g[NG0(x0) ] : Then jG1j = \u2013(G0) + 1 6 2k + 1 6 2(k + 1) = 4m. By the minimal- ity of G0, contracting any edge x0y of G0 will result in the loss of at least k + 1 edges. The vertices x0 and y thus have at least k common neighbours, so \u2013(G1) > k+ 1 = 2m (Fig. 8.1.4). NG0(x0) x0 y ( > k Fig. 8.1.4. The graph G1 4 G: a flrst approximation to the desired minor H If k is even, we let m := k=2 and G1 := G0 [NG0(x0) ] : Then jG1j = \u2013(G0) 6 2k = 4m, and \u2013(G1) > k = 2m as before. 8.1 Topological minors 175 Thus in either case we have found an integer m > k=2 and a graph m G1 4 G such that G1 jG1j 6 4m (1) and \u2013(G1) > 2m, so "(G1) > m > k=2 > 3 : (2) As 2\u2013(G1) > 4m > jG1j, our graph G1 is already quite a good candidate for the desired minor H of G. In order to jack up its value of 2\u2013 by another 16k (as required for H), we shall reapply the above contraction process to G1, and a little more rigorously than before: step by step, we shall contract edges as long as this results in a loss of no more than 76m edges per vertex. In other words, we permit a loss of edges slightly greater than maintaining " > m seems to allow. (Recall that, when we contracted G to G0, we put this threshold at "(G) = k.) If this second contraction process terminates with a non-empty graph H0, then "(H0) will be at least 76m, higher than for G1! The 1 6m thus gained will su\u2013ce to give the graph H1, obtained from H0 just as G1 was obtained from G0, the desired high minimum degree. But how can we be sure that this second contraction process will indeed end with a non-empty graph? Paradoxical though it may seem, the reason is that even a permitted loss of up to 76m edges (and one vertex) per contraction step cannot destroy the m jG1j or more edges of G1 in the jG1j steps possible: the graphs with fewer than m vertices towards the end of the process would simply be too small to be able to shed their allowance of 76m edges|and, by (1), these small graphs would account for about a quarter of the process! Formally, we shall control the graphs H in the contraction process not by specifying an upper bound on the number of edges to be discarded at each step, but by flxing a lower bound for kHk in terms of jHj. This bound grows linearly from a value of just above ¡ m 2 ¢ for jHj = m to a value of less than 4m2 for jHj = 4m. By (1) and (2), H = G1 will satisfy this bound, but clearly it cannot be satisfled by any H with jHj = m; so the contraction process must stop somewhere earlier with jHj > m. To implement this approach, let f(n) := 16m(n¡m¡ 5) f and H := n H 4 G1 : kHk > m jHj+ f(jHj)¡ ¡ m 2 ¢o : H By (1), f(jG1j) 6 f(4m) = 12m2¡ 56m < ¡ m 2 ¢ ; so G1 2 H by (2). 176 8. Substructures