Pré-visualização50 páginas

of c, so c(v) 6= c(w) since g (and hence f) is nowhere zero. If e =2 T , let ! P denote the v!w path in T . Then c(w)¡ c(v) = f( !P ) = ¡f(e; w; v) 6= 0 by Lemma 6.5.2 (ii). Conversely, we now assume that G has a k-colouring c. Let us deflne c f : ! E!Z by f(e; v; w) := c(w)¡ c(v) ; f and g: ! E\u2044! Z by g(!e \u2044) := f(!e). Clearly, f satisfles (F1) and takes g values in f§1; : : : ;§(k ¡ 1) g, so by Lemma 6.5.2 (i) the same holds for g. By deflnition of f , we further have f( ! C ) = 0 for every cycle ! C with orientation. By Lemma 6.5.2 (ii), therefore, g is a k-°ow. \u2044 140 6. Flows 6.6 Tutte\u2019s °ow conjectures How can we determine the °ow number of a graph? Indeed, does every (bridgeless) graph have a °ow number, a k-°ow for some k? Can °ow numbers, like chromatic numbers, become arbitrarily large? Can we characterize the graphs admitting a k-°ow, for given k? Of these four questions, we shall answer the second and third in this section: we prove that every bridgeless graph has a 6-°ow. In particular, a graph has a °ow number if and only if it has no bridge. The ques- tion asking for a characterization of the graphs with a k-°ow remains interesting for k = 3; 4; 5. Partial answers are suggested by the following three conjectures of Tutte, who initiated algebraic °ow theory. The oldest and best known of the Tutte conjectures is his 5-°ow conjecture: Five-Flow Conjecture. (Tutte 1954) Every bridgeless multigraph has a 5-°ow. Which graphs have a 4-°ow? By Proposition 6.4.4, the 4-edge- connected graphs are among them. The Petersen graph (Fig. 6.6.1), on the other hand, is an example of a bridgeless graph without a 4-°ow: since it is cubic but not 3-edge-colourable (Ex. 19, Ch. 5), it cannot have a 4-°ow by Proposition 6.4.5 (ii). Fig. 6.6.1. The Petersen graph Tutte\u2019s 4-°ow conjecture states that the Petersen graph must be present in every graph without a 4-°ow: Four-Flow Conjecture. (Tutte 1966) Every bridgeless multigraph not containing the Petersen graph as a mi- nor has a 4-°ow. By Proposition 1.7.2, we may replace the word \u2018minor\u2019 in the 4-°ow conjecture by \u2018topological minor\u2019. 6.6 Tutte\u2019s °ow conjectures 141 Even if true, the 4-°ow conjecture will not be best possible: a K11, for example, contains the Petersen graph as a minor but has a 4-°ow, even a 2-°ow. The conjecture appears more natural for sparser graphs, and indeed the cubic graphs form an important special case. (See the notes.) A cubic bridgeless graph or multigraph without a 4-°ow (equivalent- ly, without a 3-edge-colouring) is called a snark . The 4-°ow conjecture snark for cubic graphs says that every snark contains the Petersen graph as a minor; in this sense, the Petersen graph has thus been shown to be the smallest snark. Snarks form the hard core both of the four colour theorem and of the 5-°ow conjecture: the four colour theorem is equi- valent to the assertion that no snark is planar (exercise), and it is not di\u2013cult to reduce the 5-°ow conjecture to the case of snarks.5 However, although the snarks form a very special class of graphs, none of the problems mentioned seems to become much easier by this reduction.6 Three-Flow Conjecture. (Tutte 1972) Every multigraph without a cut consisting of exactly one or exactly three edges has a 3-°ow. Again, the 3-°ow conjecture will not be best possible: it is easy to con- struct graphs with three-edge cuts that have a 3-°ow (exercise). By our duality theorem (6.5.3), all three °ow conjectures are true for planar graphs and thus motivated: the 3-°ow conjecture translates to Gro\u2dctzsch\u2019s theorem (5.1.3), the 4-°ow conjecture to the four colour theorem (since the Petersen graph is not planar, it is not a minor of a planar graph), the 5-°ow conjecture to the flve colour theorem. We flnish this section with the main result of the chapter: Theorem 6.6.1. (Seymour 1981) Every bridgeless graph has a 6-°ow. Proof . Let G = (V;E) be a bridgeless graph. Since 6-°ows on the (3.3.5) (6.1.1) (6.4.1)components of G will add up to a 6-°ow on G, we may assume that G is connected; as G is bridgeless, it is then 2-edge-connected. Note that any two vertices in a 2-edge-connected graph lie in some common even connected subgraph|for example, in the union of two edge-disjoint paths linking these vertices by Menger\u2019s theorem (3.3.5 (ii)). We shall use this fact repeatedly. 5 The same applies to another well-known conjecture, the cycle double cover con- jecture; see Exercise 13. 6 That snarks are elusive has been known to mathematicians for some time; cf. Lewis Carroll, The Hunting of the Snark , Macmillan 1876. 142 6. Flows We shall construct a sequence H0; : : : ; Hn of disjoint connected andH0; : : : ; Hn even subgraphs of G, together with a sequence F1; : : : ; Fn of non-emptyF1; : : : ; Fn sets of edges between them. The sets Fi will each contain only one or two edges, between Hi and H0 [ : : :[Hi¡1. We write Hi =: (Vi; Ei),Vi; Ei Hi := (H0 [ : : :[Hi) + (F1 [ : : :[Fi)Hi and Hi =: (V i; Ei). Note that each Hi = (Hi¡1 [Hi) +Fi is connectedV i; Ei (induction on i). Our assumption that Hi is even implies by Proposition 6.4.1 (or directly by Proposition 1.2.1) that Hi has no bridge. As H0 we choose any K1 in G. Now assume that H0; : : : ; Hi¡1 and F1; : : : ; Fi¡1 have been deflned for some i > 0. If V i¡1 = V , we terminate the construction and set i¡ 1 =: n. Otherwise, we let Xi µ V i¡1 ben minimal such that Xi 6= ; andXi flflE(Xi; V i¡1rXi)flfl 6 1 (1) (Fig. 6.6.2); such an Xi exists, because V i¡1 is a candidate. Since G is 2-edge-connected, (1) implies that E(Xi; V i¡1) 6= ;. By the mini- mality of Xi, the graph G [Xi ] is connected and bridgeless, i.e. 2-edge- connected or a K1. As the elements of Fi we pick one or two edgesFi from E(Xi; V i¡1), if possible two. As Hi we choose any connected even subgraph of G [Xi ] containing the ends in Xi of the edges in Fi. Hi Fi Xi V i¡1 V i¡1rXi Hi¡1 Fig. 6.6.2. Constructing the Hi and Fi When our construction is complete, we set Hn =: H and E0 :=H E r E(H). By deflnition of n, H is a spanning connected subgraphE0 of G. We now deflne, by \u2018reverse\u2019 induction, a sequence fn; : : : ; f0 of Z3-fn; : : : ; f0 circulations on G. For every edge e 2 E0, let ! Ce be a cycle (with orienta- ! Ce tion) in H + e containing e, and fe a positive °ow around ! Ce; formally, we let fe be a Z3-circulation on G such that f¡1e (0) = ! E r ( ! Ce [ \u2c6 Ce).fe Let fn be the sum of all these fe. Since each e0 2 E0 lies on just one offn the cycles Ce (namely, on Ce0), we have fn( !e) 6= 0 for all !e 2 !E0. 6.6 Tutte\u2019s °ow conjectures 143 Assume now that Z3-circulations fn; : : : ; fi on G have been deflned fi for some i 6 n, and that fi( !e) 6= 0 for all !e 2 !E0 [ [ j>i ! Fj ; (2) where ! Fj := f !e 2 ! E j e 2 Fj g. Our aim is to deflne fi¡1 in such a way !Fj that (2) also holds for i¡ 1. We flrst consider the case that jFij = 1, say Fi = f e g. We then e let fi¡1 := fi, and thus have to show that fi is non-zero on (the two directions of) e. Our assumption of jFij = 1 implies by the choice of Fi that G contains no Xi{V i¡1 edge other than e. Since G is 2-edge- connected, it therefore has at least|and thus, by (1), exactly|one edge e0 between Xi and V i¡1 rXi. We show that fi is non-zero on e0; as e0 f e; e0 g is a cut in G, this implies by Proposition 6.1.1 that fi is also non-zero on e. To show that fi is non-zero on e0, we use (2): we show that e0 2 E0 [Sj>i Fj , i.e. that e0 lies in no Hk and in no Fj with j 6 i. Since e0 has both ends in V i¡1, it clearly lies in no Fj with j 6 i and in no Hk with k < i. But every Hk with k > i is a subgraph of G [V i¡1 ]. Since e0 is a bridge of G [V i¡1 ] but Hk has no bridge, this means that e0 =2 Hk. Hence, fi¡1 does indeed satisfy (2) for i¡ 1