Graph Theory
322 pág.

Graph Theory


DisciplinaTeoria dos Grafos342 materiais1.556 seguidores
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