Graph Theory
322 pág.

Graph Theory

DisciplinaTeoria dos Grafos330 materiais1.549 seguidores
Pré-visualização50 páginas
Proof . Let V := fVx j x 2 V (H) g be the set of branch sets in G(3.3.1)
V; Vx corresponding to the vertices of H. For our proof that G is (k; dk=2e)-
linked, let k distinct vertices v1; : : : ; vk 2 G be given. Let us call av1; : : : ; vk
sequence P1; : : : ; Pk of disjoint paths in G a linkage if the Pi each startlinkage
in vi and end in pairwise distinct sets V 2 V; the paths Pi themselves will
be called links. Since our assumptions about H imply that jHj > k, andlink
G is k-connected, such linkages exist: just pick k vertices from pairwise
distinct sets V 2 V, and link them disjointly to f v1; : : : ; vk g by Menger\u2019s
Now let P = (P1; : : : ; Pk) be a linkage whose total number of edgesP
V 2V G [V ] is as small as possible. Thus, if f(P ) denotes theP1; : : : ; Pk
number of edges of P not lying in any G [Vx ], we choose P so as tof(P )
i=1 f(Pi). Then for every V 2 V that meets a path Pi 2 P
there exists one such path that ends in V : if not, we could terminate Pi
in V and reduce f(Pi). Thus, exactly k of the branch sets of H meet a
link. Let us divide these sets into two classes:
U := fV 2 V j V meets exactly one link g
W := fV 2 V j V meets more than one link g :
Since H is dense and each U 2 U meets only one link, it will be easy to
show that the starting vertices vi of those links form a linked set in G.
Hence, our aim is to show that jUj > dk=2e, i.e. that U is no smaller
than W. (Recall that jUj+ jWj = k.) To this end, we flrst prove the
Every V 2 W is met by some link which leaves V again
and next meets a set from U (where it ends). (1)
Suppose Vx 2 W is a counterexample to (1). Sincex
2\u2013(H) > jHj+ 32k > \u2013(H) + 32k ;
we have \u2013(H) > 32k. As jU [Wj = k, this implies that x has a neighbour
y in H with Vy 2 V r (U [W); let wxwy be an edge of G with wx 2 Vx
and wy 2 Vy. Let Q = w : : : wxwy be a path in G [Vx [fwy g ] of whose
vertices only w lies on any link, say on Pi (Fig. 8.1.2). Replacing Pi inPi
P by P 0i := PiwQ then yields another linkage.P 0i
If Pi is not the link ending in Vx, then f(P 0i ) 6 f(Pi). The choice
of P then implies that f(P 0i ) = f(Pi), i.e. that Pi ends in the branch set
W it enters immediately after Vx. Since Vx is a counterexample to (1)
we have W =2 U , i.e. W 2 W. Let P 6= Pi be another link meeting W .
Then P does not end in W (because Pi ends there); let P 0 µ P be the
(minimal) initial segment of P that ends in W . If we now replace Pi and
P by P 0i and P
0 in P, we obtain a linkage contradicting the choice of P.
8.1 Topological minors 173
Vx 2W
P 0 W 2W
Vy 2 V r (U [W)
P 0i
Fig. 8.1.2. If Pi does not end in Vx, we replace Pi and P by P
and P 0
We now assume that Pi does end in Vx; then f(P 0i ) = f(Pi) + 1.
As Vx 2 W, there exists a link Pj that meets Vx and leaves it again; let
P 0j be the initial segment of Pj ending in Vx (Fig 8.1.3). Then f(P
j) 6
f(Pj)¡ 1. In fact, since replacing Pi and Pj with P 0i and P 0j in P yields
another linkage, the choice of P implies that f(P 0j) = f(Pj)¡ 1, so Pj
ends in the branch set W it enters immediately after Vx. Then W 2 W
as before, so we may deflne P and P 0 as before. Replacing Pi, Pj and P
by P 0i , P
j and P
0 in P, we flnally obtain a linkage that contradicts the
choice of P. This completes the proof of (1).
P 0 W 2W
Vy 2 V r (U [W)
P 0j
Vx 2W
P 0i
Fig. 8.1.3. If Pi ends in Vx, we replace Pi; Pj ; P by P
i ; P
j ; P
With the help of (1) we may deflne an injection W!U as follows:
given W 2 W, choose a link that passes through W and next meets a
set U 2 U , and map W 7! U . (This is indeed an injection, because
difierent links end in difierent branch sets.) Thus jUj > jWj, and hence
jUj > dk=2e.
Let us assume the enumeration of v1; : : : ; vk to be such that the
flrst u := jUj of the links P1; : : : ; Pk end in sets from U . Since 2\u2013(H) > u
174 8. Substructures in Sparse Graphs
jHj+ 32k, we can flnd for any two sets Vx; Vy 2 U at least 32k sets Vz such
that xz; yz 2 E(H). At least k=2 of these sets Vz do not lie in U [W.
Thus whenever U1; : : : ; U2h are distinct sets in U (so h 6 u=2 6 k=2), we
may flnd inductively h distinct sets V i 2 Vr (U [W) (i = 1; : : : ; h) such
that V i is joined in G to both U2i¡1 and U2i. For each i, any vertex of
U2i¡1 can be linked by a path through V i to any desired vertex of U2i,
and these paths will be disjoint for difierent i. Joining up the appropriate
pairs of paths from P in this way, we see that the set f v1; : : : ; vu g is
linked in G, and the lemma is proved. \u2044
Lemma 8.1.3. Let k > 6 be an integer. Then every graph G with
"(G) > k has a minor H such that 2\u2013(H) > jHj+ 16k.
Proof . We begin by choosing a (4-)minimal minor G0 of G withG0
"(G0) > k. The minimality of G0 implies that \u2013(G0) > k and "(G0) = k
(otherwise we could delete a vertex or an edge of G0), and hence
k+ 1 6 \u2013(G0) 6 d(G0) = 2k :
Let x0 2 G0 be a vertex of minimum degree.x0
If k is odd, let m := (k+ 1)=2 and
G1 := G0 [ fx0 g[NG0(x0) ] :
Then jG1j = \u2013(G0) + 1 6 2k + 1 6 2(k + 1) = 4m. By the minimal-
ity of G0, contracting any edge x0y of G0 will result in the loss of at
least k + 1 edges. The vertices x0 and y thus have at least k common
neighbours, so \u2013(G1) > k+ 1 = 2m (Fig. 8.1.4).
y (
> k
Fig. 8.1.4. The graph G1 4 G: a flrst approximation to the
desired minor H
If k is even, we let m := k=2 and
G1 := G0 [NG0(x0) ] :
Then jG1j = \u2013(G0) 6 2k = 4m, and \u2013(G1) > k = 2m as before.
8.1 Topological minors 175
Thus in either case we have found an integer m > k=2 and a graph m
G1 4 G such that G1
jG1j 6 4m (1)
and \u2013(G1) > 2m, so
"(G1) > m > k=2 > 3 : (2)
As 2\u2013(G1) > 4m > jG1j, our graph G1 is already quite a good
candidate for the desired minor H of G. In order to jack up its value
of 2\u2013 by another 16k (as required for H), we shall reapply the above
contraction process to G1, and a little more rigorously than before: step
by step, we shall contract edges as long as this results in a loss of no
more than 76m edges per vertex. In other words, we permit a loss of edges
slightly greater than maintaining " > m seems to allow. (Recall that,
when we contracted G to G0, we put this threshold at "(G) = k.) If this
second contraction process terminates with a non-empty graph H0, then
"(H0) will be at least 76m, higher than for G1! The
6m thus gained will
su\u2013ce to give the graph H1, obtained from H0 just as G1 was obtained
from G0, the desired high minimum degree.
But how can we be sure that this second contraction process will
indeed end with a non-empty graph? Paradoxical though it may seem,
the reason is that even a permitted loss of up to 76m edges (and one
vertex) per contraction step cannot destroy the m jG1j or more edges
of G1 in the jG1j steps possible: the graphs with fewer than m vertices
towards the end of the process would simply be too small to be able to
shed their allowance of 76m edges|and, by (1), these small graphs would
account for about a quarter of the process!
Formally, we shall control the graphs H in the contraction process
not by specifying an upper bound on the number of edges to be discarded
at each step, but by flxing a lower bound for kHk in terms of jHj. This
bound grows linearly from a value of just above
for jHj = m to a
value of less than 4m2 for jHj = 4m. By (1) and (2), H = G1 will satisfy
this bound, but clearly it cannot be satisfled by any H with jHj = m;
so the contraction process must stop somewhere earlier with jHj > m.
To implement this approach, let
f(n) := 16m(n¡m¡ 5) f
H :=
H 4 G1 : kHk > m jHj+ f(jHj)¡
: H
By (1),
f(jG1j) 6 f(4m) = 12m2¡ 56m <
so G1 2 H by (2).
176 8. Substructures