Graph Theory
322 pág.

Graph Theory


DisciplinaTeoria dos Grafos342 materiais1.556 seguidores
Pré-visualização50 páginas
(3.3.1), G contains disjoint paths P1; : : : ; Pk,
Q1; : : : ; Qk, such that each Pi starts in si, each Qi starts in ti, and allPi; Qi
these paths end in U but have no inner vertices in U . Let the set P ofP
these paths be chosen so that their total number of edges outside E(K)
is as small as possible.
Let u1; : : : ; uk be those k vertices in U that are not an end of aui
path in P. For each i = 1; : : : ; k, let Li be the U -path in K (i.e., theLi
subdivided edge of the K3k) from ui to the end of Pi in U , and let vi bevi
the flrst vertex of Li on any path P 2 P. By deflnition of P, P has no
more edges outside E(K) than PviLiui does, so viP = viLi and hence
P = Pi (Fig. 3.6.1). Similarly, if Mi denotes the U -path in K from uiMi
to the end of Qi in U , and wi denotes the flrst vertex of Mi on anywi
path in P, then this path is Qi. Then the paths siPiviLiuiMiwiQiti are
disjoint for difierent i and show that G is k-linked. \u2044
3.6 Paths between given pairs of vertices 63
si
Pi
P
Li
vi
ui
Mi
Qi ti
wi
Fig. 3.6.1. Constructing an si{ti path via ui
In our proof of Theorem 3.6.2 we did not try to flnd any particularly
good bound on the connectivity needed to force a graph to be k-linked;
the function f we used grows exponentially in k. Not surprisingly, this
is far from being best possible. It is still remarkable, though, that f can
in fact be chosen linear: as Bollob¶as & Thomason (1996) have shown,
every 22k-connected graph is k-linked.
Exercises
For the flrst three exercises, let G be a graph and a; b 2 V (G). Suppose that
X µ V (G)rf a; b g separates a from b in G. We say that X separates a from b
minimally if no proper subset of X separates a from b in G.
1.¡ Show that X separates a from b minimally if and only if every vertex
in X has a neighbour in the component Ca of G¡X containing a, and
another in the component Cb of G¡X containing b.
2. Let X 0 µ V (G)r f a; b g be another set separating a from b, and deflne
C0a and C
0
b correspondingly. Show that both
Ya := (X \C0a)[ (X \X 0)[ (X 0 \Ca)
and
Yb := (X \C0b)[ (X \X 0)[ (X 0 \Cb)
separate a from b (see flgure).
X0
XX0
a bYa
X
3. Do Ya and Yb separate a from b minimally if X and X
0 do? Are jYaj
and jYbj minimal for vertex sets separating a from b if jXj and jX 0j are?
4. Let X and X 0 be minimal separating vertex sets in G such that X
meets at least two components of G¡X 0. Show that X 0 meets all the
components of G¡X, and that X meets all the components of G¡X 0.
64 3. Connectivity
5.¡ Prove the elementary properties of blocks mentioned at the beginning
of Section 3.1.
6. Show that the block graph of any connected graph is a tree.
7. Show, without using Menger\u2019s theorem, that any two vertices of a 2-
connected graph lie on a common cycle.
8. For edges e; e0 2 G write e » e0 if either e = e0 or e and e0 lie on some
common cycle in G. Show that » is an equivalence relation on E(G)
whose equivalence classes are the edge sets of the non-trivial blocks
of G.
9. Let G be a 2-connected graph but not a triangle, and let e be an edge
of G. Show that either G¡ e or G=e is again 2-connected.
10. Let G be a 3-connected graph, and let xy be an edge of G. Show that
G=xy is 3-connected if and only if G¡fx; y g is 2-connected.
11. (i) Show that every cubic 3-edge-connected graph is 3-connected.
(ii) Show that a graph is cubic and 3-connected if and only if it can
be constructed from a K4 by successive applications of the following
operation: subdivide two edges by inserting a new vertex on each of
them, and join the two new subdividing vertices by an edge.
12.¡ Show that Menger\u2019s theorem is equivalent to the following statement.
For every graph G and vertex sets A;B µ V (G), there exist a set P of
disjoint A{B paths in G and a set X µ V (G) separating A from B in
G such that X has the form X = fxP j P 2 P g with xP 2 P for all
P 2 P.
13. Work out the details of the proof of Corollary 3.3.4 (ii).
14. Let k > 2. Show that every k-connected graph of order at least 2k
contains a cycle of length at least 2k.
15. Let k > 2. Show that in a k-connected graph any k vertices lie on a
common cycle.
16. Derive the edge part of Corollary 3.4.2 from the vertex part.
(Hint. Consider the H-paths in the graph obtained from the disjoint
union of H and the line graph L(G) by adding all the edges he such
that h is a vertex of H and e 2 E(G)rE(H) is an edge at h.)
17.¡ To the disjoint union of the graph H = K2m+1 with k copies of K2m+1
add edges joining H bijectively to each of the K2m+1. Show that the
resulting graph G contains at most km = 1
2
\u2022G(H) independent H-
paths.
18. Find a bipartite graph G, with partition classes A and B say, such that
for H := G [A ] there are at most 1
2
\u201aG(H) edge-disjoint H-paths in G.
Exercises 65
19.+ Derive Tutte\u2019s 1-factor theorem (2.2.1) from Mader\u2019s theorem.
(Hint. Extend the given graph G to a graph G0 by adding, for each
vertex v 2 G, a new vertex v0 and joining v0 to v. Choose H µ G0 so that
the 1-factors in G correspond to the large enough sets of independent
H-paths in G0.)
20. Find the error in the following short \u2018proof\u2019 of Theorem 3.5.1. Call a
partition non-trivial if it has at least two classes and at least one of the
classes has more than one element. We show by induction on jV j+ jEj
that G = (V;E) has k edge-disjoint spanning trees if every non-trivial
partition of V into r sets (say) has at least k(r¡ 1) cross-edges. The
induction starts trivially with G = K1 if we allow k copies of K1 as a
family of k edge-disjoint spanning trees of K1. We now consider the
induction step. If every non-trivial partition of V into r sets (say) has
more than k(r¡1) cross-edges, we delete any edge of G and are done by
induction. So V has a non-trivial partition fV1; : : : ; Vr g with exactly
k(r ¡ 1) cross-edges. Assume that jV1j > 2. If G0 := G [V1 ] has k
disjoint spanning trees, we may combine these with k disjoint spanning
trees that exist in G=V1 by induction. We may thus assume that G
0
has no k disjoint spanning trees. Then by induction it has a non-trivial
vertex partition fV 01 ; : : : ; V 0s g with fewer than k(s ¡ 1) cross-edges.
Then fV 01 ; : : : ; V 0s ; V2; : : : ; Vr g is a non-trivial vertex partition of G into
r+ s¡ 1 sets with fewer than k(r¡ 1) + k(s¡ 1) = k((r+ s¡ 1)¡ 1)
cross-edges, a contradiction.
21.¡ Show that every k-linked graph is (2k¡ 1)-connected.
Notes
Although connectivity theorems are doubtless among the most natural, and
also the most applicable, results in graph theory, there is still no comprehensive
monograph on this subject. Some areas are covered in B. Bollob¶as, Extremal
Graph Theory , Academic Press 1978, in R. Halin, Graphentheorie, Wissen-
schaftliche Buchgesellschaft 1980, and in A. Frank\u2019s chapter of the Handbook of
Combinatorics (R.L. Graham, M. Gro\u2dctschel & L. Lov¶asz, eds.), North-Holland
1995. A survey speciflcally of techniques and results on minimally k-connected
graphs (see below) is given by W. Mader, On vertices of degree n in minimally
n-connected graphs and digraphs, in (D. Mikl¶os, V.T. S¶os & T. Sz}onyi, eds.)
Paul Erd}os is 80, Vol. 2, Proc. Colloq. Math. Soc. J¶anos Bolyai, Budapest 1996.
Our proof of Tutte\u2019s Theorem 3.2.3 is due to C. Thomassen, Planarity and
duality of flnite and inflnite graphs, J. Combin. Theory B 29 (1980), 244{271.
This paper also contains Lemma 3.2.1 and its short proof from flrst principles.
(The lemma\u2019s assertion, of course, follows from Tutte\u2019s wheel theorem|its
signiflcance lies in its independent proof, which has shortened the proofs of
both of Tutte\u2019s theorems considerably.)
An approach to the study of connectivity not touched upon in this chap-
ter is the investigation of minimal k-connected graphs, those that lose their
k-connectedness as soon as we delete an edge. Like all k-connected graphs,