Pré-visualização50 páginas

in the case considered. It remains to consider the case that jFij = 2, say Fi = f e1; e2 g. e1; e2 Since Hi and Hi¡1 are both connected, we can flnd a cycle C in Hi = C (Hi[Hi¡1) +Fi that contains e1 and e2. If fi is non-zero on both these edges, we again let fi¡1 := fi. Otherwise, there are directions !e1 and !e2 of e1 and e2 such that, without loss of generality, fi( !e1) = 0 and fi( !e2) 2 f 0; 1 g. Let ! C be the orientation of C with !e2 2 ! C , and let g be a °ow of value 1 around ! C (formally: let g be a Z3-circulation on G such that g(!e2) = 1 and g¡1(0) = ! E r ( ! C [ \u2c6C )). We then let fi¡1 := fi + g. By choice of the directions !e1 and !e2, fi¡1 is non-zero on both edges. Since fi¡1 agrees with fi on all of ! E0 [Sj>i !Fj and (2) holds for i, we again have (2) also for i¡ 1. Eventually, f0 will be a Z3-circulation on G that is nowhere zero except possibly on edges of H0 [ : : :[Hn. Composing f0 with the map h 7! 2h from Z3 to Z6 (h 2 f 1; 2 g), we obtain a Z6-circulation f on G f with values in f 0; 2; 4 g for all edges lying in some Hi, and with values in f 2; 4 g for all other edges. Adding to f a 2-°ow on each Hi (formally: a Z6-circulation on G with values in f 1;¡1 g on the edges of Hi and 0 otherwise; this exists by Proposition 6.4.1), we obtain a Z6-circulation on G that is nowhere zero. Hence, G has a 6-°ow by Theorem 6.3.3. \u2044 144 6. Flows Exercises 1.¡ Prove Proposition 6.2.1 by induction on jSj. 2. (i)¡ Given n 2 N, flnd a capacity function for the network below such that the algorithm from the proof of the max-°ow min-cut theorem will need more than n augmenting paths W if these are badly chosen. s t (ii)+ Show that, if all augmenting paths are chosen as short as possible, their number is bounded by a function of the size of the network. 3.+ Derive Menger\u2019s Theorem 3.3.4 from the max-°ow min-cut theorem. (Hint. The edge version is easy. For the vertex version, apply the edge version to a suitable auxiliary graph.) 4.¡ Let f be an H-circulation on G and g:H!H 0 a group homomorphism. Show that g \u2013 f is an H 0-circulation on G. Is g \u2013 f an H 0-°ow if f is an H-°ow? 5.¡ Given k > 1, show that a graph has a k-°ow if and only if each of its blocks has a k-°ow. 6.¡ Show that \u2019(G=e) 6 \u2019(G) whenever G is a multigraph and e an edge of G. Does this imply that, for every k, the class of all multigraphs admitting a k-°ow is closed under taking minors? 7.¡ Work out the °ow number of K4 directly, without using any results from the text. 8. Let H be a flnite abelian group, G a graph, and T a spanning tree of G. Show that every mapping from the directions of E(G)rE(T ) to H that satisfles (F1) extends uniquely to an H-circulation on G. Do not use the 6-°ow Theorem 6.6.1 for the following three exercises. 9. Show that \u2019(G) < 1 for every bridgeless multigraph G. 10. Assume that a graph G has m spanning trees such that no edge of G lies in all of these trees. Show that \u2019(G) 6 2m. 11.+ Let G be a bridgeless connected graph with n vertices and m edges. By considering a normal spanning tree of G, show that \u2019(G) 6 m¡n+ 2. 12. Show that every graph with a Hamilton cycle has a 4-°ow. (A Hamilton cycle of G is a cycle in G that contains all the vertices of G.) 13. A family of (not necessarily distinct) cycles in a graph G is called a cycle double cover of G if every edge of G lies on exactly two of these cycles. The cycle double cover conjecture asserts that every bridgeless multigraph has a cycle double cover. Prove the conjecture for graphs with a 4-°ow. Exercises 145 14.¡ Determine the °ow number of C5 \u2044K1, the wheel with 5 spokes. 15. Find bridgeless graphs G and H = G¡ e such that 2 < \u2019(G) < \u2019(H). 16. Prove Proposition 6.4.1 without using Theorem 6.3.3. 17.+ Prove Heawood\u2019s theorem that a plane triangulation is 3-colourable if and only if all its vertices have even degree. 18.¡ Find a bridgeless graph that has both a 3-°ow and a cut of exactly three edges. 19. Show that the 3-°ow conjecture for planar multigraphs is equivalent to Gro\u2dctzsch\u2019s Theorem 5.1.3. 20. (i)¡ Show that the four colour theorem is equivalent to the non-exist- ence of a planar snark, i.e. to the statement that every cubic bridgeless planar multigraph has a 4-°ow. (ii) Can \u2018bridgeless\u2019 in (i) be replaced by \u20183-connected\u2019? 21.+ Show that a graph G = (V;E) has a k-°ow if and only if it admits an orientation D that directs, for every X µ V , at least 1=k of the edges in E(X;X) from X towards X. 22.¡ Generalize the 6-°ow Theorem 6.6.1 to multigraphs. Notes Network °ow theory is an application of graph theory that has had a major and lasting impact on its development over decades. As is illustrated already by the fact that Menger\u2019s theorem can be deduced easily from the max-°ow min-cut theorem (Exercise 3), the interaction between graphs and networks may go either way: while \u2018pure\u2019 results in areas such as connectivity, matching and random graphs have found applications in network °ows, the intuitive power of the latter has boosted the development of proof techniques that have in turn brought about theoretic advances. The standard reference for network °ows is L.R. Ford & D.R. Fulkerson, Flows in Networks, Princeton University Press 1962. A more recent and com- prehensive account is given by R.K. Ahuja, T.L. Magnanti & J.B. Orlin, Net- work °ows, Prentice-Hall 1993. For more theoretical aspects, see A. Frank\u2019s chapter in the Handbook of Combinatorics (R.L. Graham, M. Gro\u2dctschel & L. Lov¶asz, eds.), North-Holland 1995. A general introduction to graph algo- rithms is given in A. Gibbons, Algorithmic Graph Theory , Cambridge Univer- sity Press 1985. If one recasts the maximum °ow problem in linear programming terms, one can derive the max-°ow min-cut theorem from the linear programming duality theorem; see A. Schrijver, Theory of integer and linear programming , Wiley 1986. The more algebraic theory of group-valued °ows and k-°ows has been developed largely by Tutte; he gives a thorough account in his monograph W.T. Tutte, Graph Theory , Addison-Wesley 1984. Tutte\u2019s °ow conjectures are 146 6. Flows covered also in F. Jaeger\u2019s survey, Nowhere-zero7 °ow problems, in (L.W. Bei- neke & R.J. Wilson, eds.) Selected Topics in Graph Theory 3, Academic Press 1988. For the °ow conjectures, see also T.R. Jensen & B. Toft, Graph Coloring Problems, Wiley 1995. Seymour\u2019s 6-°ow theorem is proved in P.D. Seymour, Nowhere-zero 6-°ows, J. Combin. Theory B 30 (1981), 130{135. This pa- per also indicates how Tutte\u2019s 5-°ow conjecture reduces to snarks. In 1998, Robertson, Sanders, Seymour and Thomas announced a proof of the 4-°ow conjecture for cubic graphs. Finally, Tutte discovered a 2-variable polynomial associated with a graph, which generalizes both its chromatic polynomial and its °ow polynomial. What little is known about this Tutte polynomial can hardly be more than the tip of the iceberg: it has far-reaching, and largely unexplored, connections to areas as diverse as knot theory and statistical physics. See D.J.A. Welsh, Complexity: knots, colourings and counting (LMS Lecture Notes 186), Cam- bridge University Press 1993. 7 In the literature, the term \u2018°ow\u2019 is often used to mean what we have called \u2018cir- culation\u2019, i.e. °ows are not required to be nowhere zero unless this is stated explicitly. 7 Substructures in Dense Graphs In this chapter and the next, we study how global parameters of a graph, such as its edge density or chromatic number, have a bearing on the existence of certain local substructures. How many edges, for instance, do we have to give a graph on n vertices to be sure that, no matter how these edges happen to be arranged, the graph will contain a Kr subgraph for some given r? Or at least a Kr minor? Or a topological Kr minor? Will some su\u2013ciently high average degree or chromatic