Graph Theory
322 pág.

Graph Theory


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