Graph Theory
322 pág.

Graph Theory


DisciplinaTeoria dos Grafos328 materiais1.545 seguidores
Pré-visualização50 páginas
replace x or y by ve; this cycle, too, will
be denoted by C=e. Thus, as long as C is not a fundamental triangle,
C=e will always denote a unique cycle in G0. Note, however, that in the C=e
case of e =2 C the edge set of C=e when viewed as a subset of E(G) need
not coincide with E(C), or even be a cycle at all; an example is shown
in Figure 3.2.3.
e0
e0
C=e
ve
C
e00 e
00
E(C=e) µ G
x
y
x
y
u w u w u w
Fig. 3.2.3. One of the four possibilities for E(C=e) when e =2 C
Let us refer to the non-separating induced cycles in G or G0 as basic basic cycles
cycles. An element of C(G) will be called good if it is a linear combination good
of basic cycles in G; we thus want to show that every element of C(G) is
good. The basic idea of our proof is to contract a given cycle C 2 C(G)
to C=e, generate C=e in C(G0) by induction, and try to lift the generators
back to basic cycles in G that generate C.
We start by proving three auxiliary facts.
Every fundamental triangle is a basic cycle in G. (1)
48 3. Connectivity
A fundamental triangle, wxyw say, is clearly induced in G. If it sepa-
rated G, then f ve; w g would separate G0, which contradicts the choice
of e. This proves (1).
If C µ G is an induced cycle but not a fundamental trian-
gle, then C+C=e+D 2 f ;; feg g for some good D 2 C(G). (2)
The gist of (2) is that, in terms of \u2018generatability\u2019, C and C=e difier only
a little: after the addition of a permissible error term D, at most in the
edge e. In which other edges, then, can C and C=e difier? Clearly at
most in the two edges eu = uve and ew = vew incident with ve in C=e;
cf. Fig. 3.2.3. But these difierences between the edge sets of C=e and
C are levelled out precisely by adding the corresponding fundamental
triangles uxy and xyw (which are basic by (1)). Indeed, let Du denote
the triangle uxy if eu =2 C and ; otherwise, and let Dw denote xyw if
ew =2 C and ; otherwise. Then D := Du +Dw satisfles (2) as desired.
Next, we show how to lift basic cycles of G0 back to G:
For every basic cycle C 0 µ G0 there exists a basic cycle
C = C(C 0) µ G with C=e = C 0. (3)
If ve =2 C 0, then (3) is satisfled with C := C 0. So we assume that ve 2 C 0.
Let u and w be the two neighbours of ve on C 0, and let P be the u{wu;w
path in C 0 avoiding ve (Fig. 3.2.4). Then P µ G.P
x
y
u w
P
Fig. 3.2.4. The search for a basic cycle C with C=e = C0
We flrst assume that fux; uy; wx;wy g µ E(G), and consider (as
candidates for C) the cycles Cx := uPwxu and Cy := uPwyu. Both areCx; Cy
induced cycles in G (because C 0 is induced in G0), and clearly Cx=e =
Cy=e = C 0. Moreover, neither of these cycles separates two vertices
of G¡ (V (P ) [ fx; y g) in G, since C 0 does not separate such vertices
in G0. Thus, if Cx (say) is a separating cycle in G, then one of the
components of G¡ Cx consists just of y. Likewise, if Cy separates G
then one of the arising components contains only x. However, this cannot
happen for both Cx and Cy at once: otherwise NG(fx; y g) µ V (P ) and
hence NG(fx; y g) = fu;w g (since C 0 has no chord), which contradicts
\u2022(G) > 3. Hence, at least one of Cx, Cy is a basic cycle in G.
3.2 The structure of 3-connected graphs 49
It remains to consider the case that fux; uy; wx;wy g 6µ E(G), say
ux =2 E(G). Then, as above, either uPwyu or uPwxyu is a basic cycle
in G, according as wy is an edge of G or not. This completes the proof
of (3).
We now come to the main part of our proof, the proof that every
C 2 C(G) is good. By Proposition 1.9.1 we may assume that C is an C
induced cycle in G. By (1) we may further assume that C is not a
fundamental triangle; so C=e is a cycle. Our aim is to argue as follows.
By (2), C difiers from C=e at most by some good error term D (and
possibly in e); by (3), the basic cycles C 0i of G
0 that sum to C=e by
induction can be contracted from basic cycles of G, which likewise difier
from the C 0i only by a good error term Di (and possibly in e); hence these
basic cycles of G and all the error terms together sum to C|except that
the edge e will need some special attention.
By the induction hypothesis, C=e has a representation
C=e = C 01 + : : :+C
0
k C
0
1; : : : ; C
0
k
in C(G0), where every C 0i is a basic cycle in G0. For each i, we obtain from
(3) a basic cycle C(C 0i) µ G with C(C 0i)=e = C 0i (in particular, C(C 0i) is
not a fundamental triangle), and from (2) some good Di 2 C(G) such
that
C(C 0i) +C
0
i +Di 2 f ;; feg g : (4)
We let
Ci := C(C 0i) +Di ; C1; : : : ; Ck
then Ci is good, and by (4) it difiers from C 0i at most in e. Again by (2),
we have
C +C=e+D 2 f ;; feg g
for some good D 2 C(G), i.e. C +D difiers from C=e at most in e. But D
then C+D+C1 + : : :+Ck difiers from C=e+C 01 + : : :+C
0
k = ; at most
in e, that is,
C +D+C1 + : : :+Ck 2 f ;; feg g :
Since C +D+C1 + : : :+Ck 2 C(G) but feg =2 C(G), this means that in
fact
C +D+C1 + : : :+Ck = ; ;
so C = D+C1 + : : :+Ck is good. \u2044
50 3. Connectivity
3.3 Menger\u2019s theorem
The following theorem is one of the cornerstones of graph theory.
Theorem 3.3.1. (Menger 1927)
Let G = (V;E) be a graph and A;B µ V . Then the minimum number
[ 3.6.2 ]
[ 8.1.2 ]
[ 12.3.9 ]
[ 12.4.4 ]
[ 12.4.5 ]
of vertices separating A from B in G is equal to the maximum number
of disjoint A{B paths in G.
We ofier three proofs. WheneverG;A;B are given as in the theorem,
we denote by k = k (G;A;B) the minimum number of vertices separatingk
A from B in G. Clearly, G cannot contain more than k disjoint A{B
paths; our task will be to show that k such paths exist.
First proof. We prove the following stronger statement:
If P is any set of fewer than k disjoint A{B paths in G
then there is a set Q of jPj+ 1 disjoint A{B paths whose
set of ends includes the set of ends of the paths in P.
Keeping G and A flxed, we let B vary and apply induction on jG¡Bj.
Let R be an A{B path that avoids the (fewer than k) vertices of B that
lie on a path in P. If R avoids all the paths in P, then Q := P [ fR g
is as desired. (This will happen for jG¡Bj = 0 when all A{B paths are
trivial.) If not, let x be the last vertex of R that lies on some P 2 P
(Fig. 3.3.1). Put B0 := B [V (xP [xR) and P 0 := ¡P r fP g¢[fPx g.
Then jP 0j = jPj and k(G;A;B0) > k(G;A;B), so by the induction
hypothesis there is a set Q0 of jPj+ 1 disjoint A{B0 paths whose ends
include those of the paths in P 0. Then Q0 contains a path Q ending in x,
and a unique path Q0 whose last vertex y is not among the last vertices
of the paths in P 0. If y =2 xP , we let Q be obtained from Q0 by adding
xP to Q, and adding yR to Q0 if y =2 B. Otherwise y 2 \u201dxP , and we let
Q be obtained from Q0 by adding xR to Q and adding yP to Q0. \u2044
A B
R
P
x Px
Rx
P
Fig. 3.3.1. Paths in the flrst proof of Menger\u2019s theorem
3.3 Menger\u2019s theorem 51
Second proof. We show by induction on jGj+ kGk that G contains k
disjoint A{B paths. For all G;A;B with k 2 f 0; 1 g this is true. For
the induction step let G;A;B with k > 2 be given, and assume that the
assertion holds for graphs with fewer vertices or edges.
If there is a vertex x 2 A\B, then G¡x contains k¡1 disjoint A{B
paths by the induction hypothesis. (Why?) Together with the trivial
path fx g, these form the desired paths in G. We shall therefore assume
that
A\B = ; : (1)
We flrst construct the desired paths for the case that A and B are
separated by a set X µ V with jXj = k and X 6= A;B. Let CA be X
the union of all the components of G¡X meeting A; note that CA 6= ;,
since jAj > k = jXj but A 6= X. The subgraph CB deflned likewise is not CA; CB
empty either, and CA\CB = ;. Let us write GA := G [V (CA)[X ] and
GB := G [V (CB) [X ]. Since every A{B path in G contains an A{X GA; GB
path in GA, we cannot separate A from X in GA by fewer than k vertices.
Thus, by the induction hypothesis,