Graph Theory
322 pág.

Graph Theory


DisciplinaTeoria dos Grafos342 materiais1.554 seguidores
Pré-visualização50 páginas
GA contains k disjoint A{X paths
(Fig. 3.3.2). In the same way, there are k disjoint X{B paths in GB . As
jXj = k, we can put these paths together to form k disjoint A{B paths.
GA GB
X
A
A B
Fig. 3.3.2. Disjoint A{X paths in GA
For the general case, let P be any A{B path in G. By (1), P has
an edge ab with a =2 B and b =2 A. Let Y be a set of as few vertices as ab
possible separating A from B in G¡ab (Fig. 3.3.3). Then Ya := Y [f a g Y
and Yb := Y [f b g both separate A from B in G, and by deflnition of k Ya; Yb
we have
jYaj; jYbj > k :
If equality holds here, we may assume by the case already treated that
fYa; Yb g µ fA;B g, so fYa; Yb g = fA;B g since a =2 B and b =2 A. Thus,
Y = A\B. Since jY j > k¡ 1 > 1, this contradicts (1).
We therefore have either jYaj > k or jYbj > k, and hence jY j > k.
By the induction hypothesis, then, there are k disjoint A{B paths even
in G¡ ab µ G. \u2044
52 3. Connectivity
A B
Y
P
a b
Fig. 3.3.3. Separating A from B in G¡ ab
Applied to a bipartite graph, Menger\u2019s theorem specializes to the
assertion of Ko\u2dcnig\u2019s theorem (2.1.1). For our third proof, we now adapt
the alternating path proof of Ko\u2dcnig\u2019s theorem to the more general set-
up of Theorem 3.3.1. Let again G;A;B be given, and let P be a set ofP
disjoint A{B paths in G. We write
V [P ] :=
[
fV (P ) j P 2 P g
E [P ] :=
[
fE(P ) j P 2 P g :
A walk W = x0e0x1e1 : : : en¡1xn in G with ei 6= ej for i 6= j is said
to be alternating with respect to P if the following three conditions are
satisfled for all i < n (Fig. 3.3.4):alternatingwalk
(i) if ei = e 2 E [P ], then W traverses the edge e backwards, i.e.
xi+1 2 P\u201dxi for some P 2 P;
(ii) if xi = xj with i 6= j, then xi 2 V [P ];
(iii) if xi 2 V [P ], then f ei¡1; ei g\E [P ] 6= ;.2
Px0
xn
A
B
W
Fig. 3.3.4. An alternating walk from A to B
2 For i = 0 we let f ei¡1; ei g := f e0 g.
3.3 Menger\u2019s theorem 53
Let us consider a walk W = x0e0x1e1 : : : en¡1xn from Ar V [P ] W;xi; ei
to BrV [P ], alternating with respect to P. By (ii), any vertex outside
V [P ] occurs at most once on W . Since the edges ei of W are all distinct,
(iii) implies that any vertex in V [P ] occurs at most twice on W . This
can happen in two ways: if xi = xj with 0 < i < j < n, say, then
either ei¡1; ej 2 E [P ] and ei; ej¡1 =2 E [P ]
or ei; ej¡1 2 E [P ] and ei¡1; ej =2 E [P ] :
Lemma 3.3.2. If such a walk W exists, then G contains jPj+1 disjoint
A{B paths.
Proof . Let H be the graph on V [P ][fx0; : : : ; xn g whose edge set is the
symmetric difierence of E [P ] with f e0; : : : ; en¡1 g. In H, the ends of
the paths in P and of W have degree 1 (or 0, if the path or W is trivial),
and all other vertices have degree 0 or 2. For each of the jPj+ 1 vertices
a 2 (A\ V [P ])[ fx0 g, therefore, the component of H containing a is
a path, P = v0 : : : vk say, which starts in a and ends in A or B. Using P
conditions (i) and (iii), one easily shows by induction on i = 0; : : : ; k¡ 1
that P traverses each of its edges e = vivi+1 in the forward direction with
respect to P or W . (Formally: if e 2 P 0 with P 0 2 P, then vi 2 P 0\u201dvi+1;
if e = ej 2 W , then vi = xj and vi+1 = xj+1.) Hence, P ends in B. As
we have jPj+ 1 disjoint such paths P , this completes the proof. \u2044
Third proof of Menger\u2019s theorem. Let P be a set of as many disjoint P
A{B paths in G as possible. Unless otherwise stated, all alternating
walks considered are alternating with respect to P. We set
A1 := A\V [P ] and A2 := ArA1 ; A1; A2
and
B1 := B \V [P ] and B2 := BrB1 : B1; B2
For every path P 2 P, let xP be the last vertex of P that lies on xP
some alternating walk starting in A2; if no such vertex exists, let xP be
the flrst vertex of P . Clearly, the set
X := fxP j P 2 P g X
has cardinality jPj; it thus su\u2013ces to show that X separates A from B.
Let Q be any A{B path in G; we show that Q meets X. Suppose Q
not. By the maximality of P, the path Q meets V [P ]. Since the A{
V [P ] path in Q is trivially an alternating walk, Q also meets the vertex
set V [P 0 ] of
P 0 := fPxP j P 2 P g ; P 0
54 3. Connectivity
let y be the last vertex of Q in V [P 0 ], let P be the path in P containing y,y; P
and let x := xP . Finally, let W be an alternating walk from A2 to x,x;W
as in the deflnition of xP . By assumption, Q avoids X and hence x,
so y 2 P\u201dx, and W [ xPyQ is a walk from A2 to B (Fig. 3.3.5). If
this walk is alternating and ends in B2, we are home: then G contains
jPj+ 1 disjoint A{B paths by Lemma 3.3.2, contrary to the maximality
of P.
P
Q
W
y
x
z Qy
Fig. 3.3.5. Alternating walks in the third proof of Menger\u2019s the-
orem
How could W [ xPyQ fail to be an alternating walk? For a start,
W might already use an edge of xPy. But if x0 is the flrst vertex of W
on xP\u201dy, then W 0 := Wx0Py is an alternating walk from A2 to y. (Byx0;W 0
Wx0 we mean the initial segment of W ending at the flrst occurrence of
x0 on W ; from there onwards, W 0 follows P back to y.) Even our new
walk W 0yQ need not yet be alternating: W 0 might still meet \u201dyQ. By
deflnition of P 0 and W , however, and the choice of y on Q, we have
V (W 0)\V [P ] µ V [P 0 ] and V (\u201dyQ)\V [P 0 ] = ; :
Thus, W 0 and \u201dyQ can meet only outside P.
If W 0 does indeed meet \u201dyQ, let z be the flrst vertex of W 0 on \u201dyQ. Asz
z lies outside V [P ], it occurs only once on W 0 (condition (ii)), and we let
W 00 := W 0zQ. On the other hand if W 0\\u201dyQ = ;, we set W 00 := W 0[yQ.W 00
In both cases, W 00 is alternating with respect to P 0, becauseW 0 is and \u201dyQ
avoids V [P 0 ]. (Note that W 00 satisfles condition (iii) at y in the second
case, while in the flrst case (iii) is not applicable to z.) By deflnition of P 0,
therefore, W 00 avoids V [P ]r V [P 0 ]; in particular, V (\u201dyQ)\ V [P ] = ;.
Thus W 00 is also alternating with respect to P, and it ends in B2. (Note
that y cannot be the last vertex of W 00, since y 2 P\u201dx and hence y =2 B.)
Furthermore, W 00 starts in A2, because W does. We may therefore
use W 00 with Lemma 3.3.2 to obtain the desired contradiction to the
maximality of P. \u2044
3.3 Menger\u2019s theorem 55
A set of a{B paths is called an a{B fan if any two of the paths have fan
only a in common.
Corollary 3.3.3. For B µ V and a 2 V rB, the minimum number of [ 10.1.2 ]
vertices 6= a separating a from B in G is equal to the maximum number
of paths forming an a{B fan in G.
Proof . Apply Theorem 3.3.1 with A := N(a). \u2044
Corollary 3.3.4. Let a and b be two distinct vertices of G.
(i) If ab =2 E, then the minimum number of vertices 6= a; b separating
a from b in G is equal to the maximum number of independent
a{b paths in G.
(ii) The minimum number of edges separating a from b in G is equal
to the maximum number of edge-disjoint a{b paths in G.
Proof . (i) Apply Theorem 3.3.1 with A := N(a) and B := N(b).
(ii) Apply Theorem 3.3.1 to the line graph of G, with A := E(a)
and B := E(b). \u2044
Theorem 3.3.5. (Global Version of Menger\u2019s Theorem)
[ 4.2.10 ]
[ 6.6.1 ]
[ 9.4.2 ](i) A graph is k-connected if and only if it contains k independent
paths between any two vertices.
(ii) A graph is k-edge-connected if and only if it contains k edge-
disjoint paths between any two vertices.
Proof . (i) If a graph G contains k independent paths between any two
vertices, then jGj > k and G cannot be separated by fewer than k ver-
tices; thus, G is k-connected.
Conversely, suppose that G is k-connected (and, in particular, has
more than k vertices) but contains vertices a; b not linked by k indepen- a; b
dent paths. By Corollary 3.3.4 (i), a and b are adjacent; let G0 := G¡ab. G0
Then G0 contains at most k ¡ 2 independent a{b paths. By Corollary
3.3.4 (i), we can separate a and b in G0 by a set X of at most k ¡ 2 X
vertices. As jGj > k, there is at least one further vertex v =2 X [f a; b g v
in G. Now X separates v in G0 from either a or