Pré-visualização50 páginas

(3.3.1), G contains disjoint paths P1; : : : ; Pk, Q1; : : : ; Qk, such that each Pi starts in si, each Qi starts in ti, and allPi; Qi these paths end in U but have no inner vertices in U . Let the set P ofP these paths be chosen so that their total number of edges outside E(K) is as small as possible. Let u1; : : : ; uk be those k vertices in U that are not an end of aui path in P. For each i = 1; : : : ; k, let Li be the U -path in K (i.e., theLi subdivided edge of the K3k) from ui to the end of Pi in U , and let vi bevi the flrst vertex of Li on any path P 2 P. By deflnition of P, P has no more edges outside E(K) than PviLiui does, so viP = viLi and hence P = Pi (Fig. 3.6.1). Similarly, if Mi denotes the U -path in K from uiMi to the end of Qi in U , and wi denotes the flrst vertex of Mi on anywi path in P, then this path is Qi. Then the paths siPiviLiuiMiwiQiti are disjoint for difierent i and show that G is k-linked. \u2044 3.6 Paths between given pairs of vertices 63 si Pi P Li vi ui Mi Qi ti wi Fig. 3.6.1. Constructing an si{ti path via ui In our proof of Theorem 3.6.2 we did not try to flnd any particularly good bound on the connectivity needed to force a graph to be k-linked; the function f we used grows exponentially in k. Not surprisingly, this is far from being best possible. It is still remarkable, though, that f can in fact be chosen linear: as Bollob¶as & Thomason (1996) have shown, every 22k-connected graph is k-linked. Exercises For the flrst three exercises, let G be a graph and a; b 2 V (G). Suppose that X µ V (G)rf a; b g separates a from b in G. We say that X separates a from b minimally if no proper subset of X separates a from b in G. 1.¡ Show that X separates a from b minimally if and only if every vertex in X has a neighbour in the component Ca of G¡X containing a, and another in the component Cb of G¡X containing b. 2. Let X 0 µ V (G)r f a; b g be another set separating a from b, and deflne C0a and C 0 b correspondingly. Show that both Ya := (X \C0a)[ (X \X 0)[ (X 0 \Ca) and Yb := (X \C0b)[ (X \X 0)[ (X 0 \Cb) separate a from b (see flgure). X0 XX0 a bYa X 3. Do Ya and Yb separate a from b minimally if X and X 0 do? Are jYaj and jYbj minimal for vertex sets separating a from b if jXj and jX 0j are? 4. Let X and X 0 be minimal separating vertex sets in G such that X meets at least two components of G¡X 0. Show that X 0 meets all the components of G¡X, and that X meets all the components of G¡X 0. 64 3. Connectivity 5.¡ Prove the elementary properties of blocks mentioned at the beginning of Section 3.1. 6. Show that the block graph of any connected graph is a tree. 7. Show, without using Menger\u2019s theorem, that any two vertices of a 2- connected graph lie on a common cycle. 8. For edges e; e0 2 G write e » e0 if either e = e0 or e and e0 lie on some common cycle in G. Show that » is an equivalence relation on E(G) whose equivalence classes are the edge sets of the non-trivial blocks of G. 9. Let G be a 2-connected graph but not a triangle, and let e be an edge of G. Show that either G¡ e or G=e is again 2-connected. 10. Let G be a 3-connected graph, and let xy be an edge of G. Show that G=xy is 3-connected if and only if G¡fx; y g is 2-connected. 11. (i) Show that every cubic 3-edge-connected graph is 3-connected. (ii) Show that a graph is cubic and 3-connected if and only if it can be constructed from a K4 by successive applications of the following operation: subdivide two edges by inserting a new vertex on each of them, and join the two new subdividing vertices by an edge. 12.¡ Show that Menger\u2019s theorem is equivalent to the following statement. For every graph G and vertex sets A;B µ V (G), there exist a set P of disjoint A{B paths in G and a set X µ V (G) separating A from B in G such that X has the form X = fxP j P 2 P g with xP 2 P for all P 2 P. 13. Work out the details of the proof of Corollary 3.3.4 (ii). 14. Let k > 2. Show that every k-connected graph of order at least 2k contains a cycle of length at least 2k. 15. Let k > 2. Show that in a k-connected graph any k vertices lie on a common cycle. 16. Derive the edge part of Corollary 3.4.2 from the vertex part. (Hint. Consider the H-paths in the graph obtained from the disjoint union of H and the line graph L(G) by adding all the edges he such that h is a vertex of H and e 2 E(G)rE(H) is an edge at h.) 17.¡ To the disjoint union of the graph H = K2m+1 with k copies of K2m+1 add edges joining H bijectively to each of the K2m+1. Show that the resulting graph G contains at most km = 1 2 \u2022G(H) independent H- paths. 18. Find a bipartite graph G, with partition classes A and B say, such that for H := G [A ] there are at most 1 2 \u201aG(H) edge-disjoint H-paths in G. Exercises 65 19.+ Derive Tutte\u2019s 1-factor theorem (2.2.1) from Mader\u2019s theorem. (Hint. Extend the given graph G to a graph G0 by adding, for each vertex v 2 G, a new vertex v0 and joining v0 to v. Choose H µ G0 so that the 1-factors in G correspond to the large enough sets of independent H-paths in G0.) 20. Find the error in the following short \u2018proof\u2019 of Theorem 3.5.1. Call a partition non-trivial if it has at least two classes and at least one of the classes has more than one element. We show by induction on jV j+ jEj that G = (V;E) has k edge-disjoint spanning trees if every non-trivial partition of V into r sets (say) has at least k(r¡ 1) cross-edges. The induction starts trivially with G = K1 if we allow k copies of K1 as a family of k edge-disjoint spanning trees of K1. We now consider the induction step. If every non-trivial partition of V into r sets (say) has more than k(r¡1) cross-edges, we delete any edge of G and are done by induction. So V has a non-trivial partition fV1; : : : ; Vr g with exactly k(r ¡ 1) cross-edges. Assume that jV1j > 2. If G0 := G [V1 ] has k disjoint spanning trees, we may combine these with k disjoint spanning trees that exist in G=V1 by induction. We may thus assume that G 0 has no k disjoint spanning trees. Then by induction it has a non-trivial vertex partition fV 01 ; : : : ; V 0s g with fewer than k(s ¡ 1) cross-edges. Then fV 01 ; : : : ; V 0s ; V2; : : : ; Vr g is a non-trivial vertex partition of G into r+ s¡ 1 sets with fewer than k(r¡ 1) + k(s¡ 1) = k((r+ s¡ 1)¡ 1) cross-edges, a contradiction. 21.¡ Show that every k-linked graph is (2k¡ 1)-connected. Notes Although connectivity theorems are doubtless among the most natural, and also the most applicable, results in graph theory, there is still no comprehensive monograph on this subject. Some areas are covered in B. Bollob¶as, Extremal Graph Theory , Academic Press 1978, in R. Halin, Graphentheorie, Wissen- schaftliche Buchgesellschaft 1980, and in A. Frank\u2019s chapter of the Handbook of Combinatorics (R.L. Graham, M. Gro\u2dctschel & L. Lov¶asz, eds.), North-Holland 1995. A survey speciflcally of techniques and results on minimally k-connected graphs (see below) is given by W. Mader, On vertices of degree n in minimally n-connected graphs and digraphs, in (D. Mikl¶os, V.T. S¶os & T. Sz}onyi, eds.) Paul Erd}os is 80, Vol. 2, Proc. Colloq. Math. Soc. J¶anos Bolyai, Budapest 1996. Our proof of Tutte\u2019s Theorem 3.2.3 is due to C. Thomassen, Planarity and duality of flnite and inflnite graphs, J. Combin. Theory B 29 (1980), 244{271. This paper also contains Lemma 3.2.1 and its short proof from flrst principles. (The lemma\u2019s assertion, of course, follows from Tutte\u2019s wheel theorem|its signiflcance lies in its independent proof, which has shortened the proofs of both of Tutte\u2019s theorems considerably.) An approach to the study of connectivity not touched upon in this chap- ter is the investigation of minimal k-connected graphs, those that lose their k-connectedness as soon as we delete an edge. Like all k-connected graphs,