Graph Theory
322 pág.

Graph Theory

DisciplinaTeoria dos Grafos383 materiais1.622 seguidores
Pré-visualização50 páginas
of Fi. If
x; y are the ends of a path in F 0i \C0, then also xFiy µ C0.
Let e = vw be the new edge in E(F 0i )rE [F ]; this is the only edge of
F 0i not lying in Fi. We assume that e 2 xF
iy: otherwise we would have
xFiy = xF 0iy and nothing to show. It su\u2013ces to show that vFiw µ C0:
then (xF 0iy¡ e)[ vFiw is a connected subgraph of Fi \C0 that contains
x; y, and hence also xFiy. Let e0 be any edge of vFiw. Since we could
replace e0 in F 2 F0 by e and obtain an element of F0 not contain-
ing e0, we have e0 2 E0. Thus vFiw µ G0, and hence vFiw µ C0 since
v; w 2 xF 0iy µ C0. This proves (1).
In order to prove that U = V (C0) is connected in F 0i we show that,
for every edge xy 2 C0, the path xF 0i y exists and lies in C
0. As C0 is
connected, the union of all these paths will then be a connected spanning
subgraph of F 0i [U ].
So let e = xy 2 C0 be given. As e 2 E0, there exist an s 2 N
and k-tuples F r = (F r1 ; : : : ; F
k ) for r = 1; : : : ; s such that each F
r is
obtained from F r¡1 by edge replacement and e 2 E rE [F s ]. Setting
60 3. Connectivity
F := F s in (1), we may think of e as a path of length 1 in F 0i \ C0.
Successive applications of (1) to F = F s; : : : ; F 0 then give xF 0i y µ C0
as desired. \u2044
Proof of Theorem 3.5.1. We prove the backward implication by(1.5.3)
induction on jGj. For jGj = 2 the assertion holds. For the induction
step, we now suppose that for every partition P of V there are at least
k (jP j¡1) cross-edges, and construct k edge-disjoint spanning trees in G.
Pick a k-tuple F 0 = (F 01 ; : : : ; F
k ) 2 F . If every F 0i is a tree, we areF 0
done. If not, we have
kF 0k =
kF 0i k < k (jGj ¡ 1)
by Corollary 1.5.3. On the other hand, we have kGk > k (jGj ¡ 1) by
assumption: consider the partition of V into single vertices. So there
exists an edge e0 2 E r E [F 0 ]. By Lemma 3.5.3, there exists a sete0
U µ V that is connected in every F 0i and contains the ends of e0; inU
particular, jU j > 2. Since every partition of the contracted multigraph
G=U induces a partition of G with the same cross-edges,3 G=U has at
least k (jP j ¡ 1) cross-edges with respect to any partition P . By the
induction hypothesis, therefore, G=U has k edge-disjoint spanning trees
T1; : : : ; Tk. Replacing in each Ti the vertex vU contracted from U by the
spanning tree F 0i \G [U ] of G [U ], we obtain k edge-disjoint spanning
trees in G. \u2044
Let us say that subgraphs G1; : : : ; Gk of a graph G partition G if
their edge sets form a partition of E(G). Our spanning tree problem may
then be recast as follows: into how many connected spanning subgraphs
can we partition a given graph? The excuse for rephrasing our simple
tree problem in this more complicated way is that it now has an obvious
dual (cf. Theorem 1.5.1): into how few acyclic (spanning) subgraphs
can we partition a given graph? Or for given k: which graphs can be
partitioned into at most k forests?
An obvious necessary condition now is that every set U µ V (G)
induces at most k (jU j ¡ 1) edges, no more than jU j ¡ 1 for each forest.
Once more, this condition turns out to be su\u2013cient too. And surprising-
ly, this can be shown with the help of Lemma 3.5.3, which was designed
for the proof of our theorem on edge-disjoint spanning trees:
Theorem 3.5.4. (Nash-Williams 1964)
A multigraph G = (V;E) can be partitioned into at most k forests if and
only if kG [U ]k 6 k (jU j ¡ 1) for every non-empty set U µ V .
3 see Chapter 1.10 on the contraction of multigraphs
3.5 Edge-disjoint spanning trees 61
Proof . The forward implication was shown above. Conversely, we show (1.5.3)
that every k-tuple F = (F1; : : : ; Fk) 2 F partitions G, i.e. that E [F ] =
E. If not, let e 2 ErE [F ]. By Lemma 3.5.3, there exists a set U µ V
that is connected in every Fi and contains the ends of e. Then G [U ]
contains jU j ¡ 1 edges from each Fi, and in addition the edge e. Thus
kG [U ]k > k (jU j ¡ 1), contrary to our assumption. \u2044
The least number of forests forming a partition of a graph G is called
the arboricity of G. By Theorem 3.5.4, the arboricity is a measure for arboricity
the maximum local density: a graph has small arboricity if and only if
it is \u2018nowhere dense\u2019, i.e. if and only if it has no subgraph H with &quot;(H)
3.6 Paths between given pairs of vertices
A graph with at least 2k vertices is said to be k-linked if for every 2k dis- k-linked
tinct vertices s1; : : : ; sk, t1; : : : ; tk it contains k disjoint paths P1; : : : ; Pk
with Pi = si : : : ti for all i. Thus unlike in Menger\u2019s theorem, we are not
merely asking for k disjoint paths between two sets of vertices: we insist
that each of these paths shall link a specifled pair of endvertices.
Clearly, every k-linked graph is k-connected. The converse, however,
is far from true: being k-linked is generally a much stronger property
than k-connectedness. But still, the two properties are related: our aim
in this section is to prove the existence of a function f :N!N such that
every f(k)-connected graph is k-linked.
As a lemma, we need a result that would otherwise belong in Chap-
ter 8:
Theorem 3.6.1. (Mader 1967)
There is a function h:N!N such that every graph with average degree
at least h(r) contains Kr as a topological minor, for every r 2 N.
Proof . For r 6 2, the assertion holds with h(r) = 1; we now assume that (1.2.2)(1.3.1)
r > 3. We show by induction on m = r; : : : ;
that every graph G with
average degree d(G) > 2m has a topological minor X with r vertices and
m edges; for m =
this implies the assertion with h(r) = 2(
If m = r then, by Propositions 1.2.2 and 1.3.1, G contains a cycle
of length at least &quot;(G) + 1 > 2r¡1 + 1 > r+ 1, and the assertion follows
with X = Cr.
Now let r < m 6
, and assume the assertion holds for smaller m.
Let G with d(G) > 2m be given; thus, &quot;(G) > 2m¡1. Since G has a
component C with &quot;(C) > &quot;(G), we may assume that G is connected.
Consider a maximal set U µ V (G) such that U is connected in G and U
62 3. Connectivity
&quot;(G=U) > 2m¡1; such a set U exists, because G itself has the form G=U
with jU j = 1. Since G is connected, we have N(U) 6= ;.
Let H := G [N(U) ]. If H has a vertex v of degree dH(v) < 2m¡1, weH
may add it to U and obtain a contradiction to the maximality of U : when
we contract the edge vvU in G=U , we lose one vertex and dH(v) + 1 6
2m¡1 edges, so &quot; will still be at least 2m¡1. Therefore d(H) > \u2013(H) >
2m¡1. By the induction hypothesis, H contains a TY with jY j = r
and kY k = m¡ 1. Let x; y be two branch vertices of this TY that are
non-adjacent in Y . Since x and y lie in N(U) and U is connected in G,
G contains an x{y path whose inner vertices lie in U . Adding this path
to the TY , we obtain the desired TX. \u2044
How can Theorem 3.6.1 help with our aim to show that high con-
nectivity will make a graph k-linked? Since high connectivity forces the
average degree up (even the minimum degree), we may assume by the
theorem that our graph contains a subdivision K of a large complete
graph. Our plan now is to use Menger\u2019s theorem to link the given ver-
tices si and ti disjointly to branch vertices of K, and then to join up the
correct pairs of those branch vertices inside K.
Theorem 3.6.2. (Jung 1970; Larman & Mani 1970)
There is a function f :N! N such that every f(k)-connected graph is
k-linked, for all k 2 N.
Proof . We prove the assertion for f(k) = h(3k) + 2k, where h is a(3.3.1)
function as in Theorem 3.6.1. Let G be an f(k)-connected graph. ThenG
d(G) > \u2013(G) > \u2022(G) > h(3k); choose K = TK3k µ G as in TheoremK
3.6.1, and let U denote its set of branch vertices.U
For the proof that G is k-linked, let distinct vertices s1; : : : ; sk andsi; ti
t1; : : : ; tk of G be given. By deflnition of f(k), we have \u2022(G) > 2k.
Hence by Menger\u2019s theorem