Pré-visualização50 páginas

in Sparse Graphs For every H 2H, any graph obtained from H by one of the following three operations will again be in H: (i) deletion of an edge, if kHk > m jHj+ f(jHj)¡ ¡m2 ¢+ 1; (ii) deletion of a vertex of degree at most 76m; (iii) contraction of an edge xy 2 H such that x and y have at most 7 6m¡ 1 common neighbours in H. Starting with G1, let us apply these operations as often as possible, and let H0 2 H be the graph obtained eventually. SinceH0 kKmk = m jKmj ¡m¡ ¡m2 ¢ and f(m) = ¡ 56m > ¡m; Km does not have enough edges to be in H; thus, H contains no graph on m vertices. Hence jH0j > m, and in particular H0 6= ;. Let x1 2 H0x1 be a vertex of minimum degree, and put H1 := H0 [ fx1 g[NH0(x1) ] :H1 We shall prove that the minimum degree of H := H1 is as large as claimed in the lemma. Note flrst that \u2013(H1) > 76m: (3) Indeed, since H0 is minimal with respect to (ii) and (iii), we have d(x1) > 7 6m in H0 (and hence in H1), and every vertex y 6= x1 of H1 has more than 76m ¡ 1 common neighbours with x1 (and hence more than 76m neighbours in H1 altogether). In order to convert (3) into the desired inequality of the form 2\u2013(H1) > jH1j+fim ; we need an upper bound for jH1j in terms of m. Since H0 lies in H but is minimal with respect to (i), we have kH0k < m jH0j+ \u2021 1 6m jH0j ¡ 16m2¡ 56m · ¡ ¡m2 ¢+ 1 = 76m jH0j ¡ 46m2¡ 13m+ 1 6 (2) 7 6m jH0j ¡ 46m2: (4) 8.1 Topological minors 177 By the choice of x1 and deflnition of H1, therefore, jH1j ¡ 1 = \u2013(H0) 6 2 "(H0) < (4) 7 3m¡ 43m2=jH0j 6 (1) 7 3m¡ 13m = 2m; so jH1j 6 2m. Hence, 2\u2013(H1) > (3) 2m+ 13m > jH1j+ 13m > (2) jH1j+ 16k as claimed. \u2044 Proof of Theorem 8.1.1. We prove the assertion for c := 1116. Let (1.4.2) G be a graph with d(G) > 1116r2. By Theorem 1.4.2, G has a subgraph G0 such that G0 \u2022(G0) > 279r2 > 276r2 + 3r : Pick a set X := fx1; : : : ; x3r g of 3r vertices in G0, and let G1 := G0¡X. X For each i = 1; : : : ; 3r choose a set Yi of 5r neighbours of xi in G1; let G1; Yi these sets Yi be disjoint for difierent i. (This is possible since \u2013(G0) > \u2022(G0) > 15r2 + jXj.) As \u2013(G1) > \u2022(G1) > \u2022(G0)¡ jXj > 276r2; we have "(G1) > 138r2. By Lemma 8.1.3, G1 has a minor H with 2\u2013(H) > jHj+ 23r2 and is therefore (15r2; 7r2)-linked by Lemma 8.1.2; let Z µ S3ri=1 Yi be a set of 7r2 vertices that is linked in G1. Z For all i = 1; : : : ; 3r let Zi := Z \ Yi. Since Z is linked, it su\u2013ces Zi to flnd r indices i with jZij > r¡ 1: then the corresponding xi will be the branch vertices of a TKr in G0. If r such i cannot be found, then jZij 6 r¡ 2 for all but at most r¡ 1 indices i. But then jZj = 3rX i=1 jZij 6 (r¡ 1) 5r+ (2r+ 1)(r¡ 2) < 7r2 = jZj ; a contradiction. \u2044 178 8. Substructures in Sparse Graphs Although Theorem 8.1.1 already gives a good estimate, it seems very di\u2013cult to determine the exact average degree needed to force a TKr subgraph, even for small r. We shall come back to the case of r = 5 in Section 8.3; more results and conjectures are given in the notes. The following almost counter-intuitive result of Mader implies that the existence of a topological Kr minor can be forced essentially by large girth. In the next section, we shall prove the analogue of this for ordinary minors. Theorem 8.1.4. (Mader 1997) For every graph H of maximum degree d > 3 there exists an integer k such that every graph G of minimum degree at least d and girth at least k contains H as a topological minor. As discussed already in Chapter 5.2 and the introduction to Chap- ter 7, no constant average degree, however large, will force an arbitrary graph to contain a given graph H as a subgraph|as long as H contains at least one cycle. By Proposition 1.2.2 and Corollary 1.5.4, on the other hand, any graph G contains all trees on up to "(G) + 2 vertices. Large average degree therefore does ensure the occurrence of any flxed tree T as a subgraph. What can we say, however, if we would like T to occur as an induced subgraph? Here, a large average degree appears to do as much harm as good, even for graphs of bounded clique number. (Consider, for example, complete bipartite graphs.) It is all the more remarkable, then, that the assumption of a large chromatic number rather than a large average degree seems to make a difierence here: according to a conjecture of Gy¶arf¶as, any graph of large enough chromatic number contains either a large complete graph or any given tree as an induced subgraph. (For- mally: for every integer r and every tree T , there exists an integer k such that every graph G with ´(G) > k and !(G) < r contains an induced copy of T .) The weaker topological version of this is indeed true: Theorem 8.1.5. (Scott 1997) For every integer r and every tree T there exists an integer k such that every graph with ´(G) > k and !(G) < r contains an induced copy of some subdivision of T . 8.2 Minors 179 8.2 Minors According to Theorem 8.1.1, an average degree of cr2 su\u2013ces to force the existence of a topological Kr minor in a given graph. If we are content with any minor, topological or not, an even smaller average degree will do: in a pioneering paper of 1968, Mader proved that every graph with an average degree of at least cr log r has a Kr minor. The following result, the analogue to Theorems 7.1.1 and 8.1.1 for general minors, determines the precise average degree needed as a function of r, up to a constant c: Theorem 8.2.1. (Kostochka 1982; Thomason 1984) There exists a c 2 R such that, for every r 2 N, every graph G of average degree d(G) > c r p log r has a Kr minor. Up to the value of c, this bound is best possible as a function of r. The easier implication of the theorem, the fact that in general an average degree of c r p log r is needed to force a Kr minor, follows from consider- ing random graphs, to be introduced in Chapter 11. The converse impli- cation, the fact that this average degree su\u2013ces, is proved by methods similar to those described in Section 8.1. Rather than proving Theorem 8.2.1, we therefore devote the remain- der of this section to another striking result on forcing minors. At flrst glance, this result is so surprising that it seems almost paradoxical: as long as we do not merely subdivide edges, we can force a Kr minor in a graph simply by raising its girth (Corollary 8.2.3)! Theorem 8.2.2. (Thomassen 1983) Given an integer k, every graph G with girth g(G) > 4k¡3 and \u2013(G) > 3 has a minor H with \u2013(H) > k. Proof . As \u2013(G) > 3, every component of G contains a cycle. In particu- (1.5.3) lar, the assertion is trivial for k 6 2; so let k > 3. Consider the vertex set V of a component of G, together with a partition fV1; : : : ; Vm g of V; Vi V into as many connected sets Vi with at least 2k¡ 2 vertices each as m possible. (Such a partition exists, since jV j > g(G) > 2k¡ 2 and V is connected in G.) We flrst show that every G [Vi ] is a tree. To this end, let Ti be a spanning tree of G [Vi ]. If G [Vi ] has an edge e =2 Ti, then Ti+e contains a cycle C; by assumption, C has length at least 4k¡3. The edge (about) opposite e on C therefore separates the path C ¡ e, and hence also Ti, into two components with at least 2k¡ 2 vertices each. Together with the sets Vj for j 6= i, these two components form a partition of V into m+ 1 sets that contradicts the maximality of m. So each G [Vi ] is indeed a tree, i.e. G [Vi ] = Ti. As \u2013(G) > 3, the Ti degrees in G of the vertices in Vi sum to at least 3 jVij, while the edges of Ti account for only 2 jVij ¡ 2 in this sum. Hence for each i, G has 180 8. Substructures in Sparse Graphs at least jVij+ 2 > 2k edges joining Vi to V r Vi. We shall prove that every Vi sends at most two edges to each of the other Vj ; then Vi must send edges to at least k of those Vj , so the Vi are the branch sets of an MH µ G with \u2013(H) >