A maior rede de estudos do Brasil

Grátis
655 pág.
Adrian-Bondy_U.S.R_Murty_Graph_Theory

Pré-visualização | Página 33 de 50

5
Nonseparable Graphs
Contents
5.1 Cut Vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.2 Separations and Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Nonseparable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Proof Technique: Splitting off Edges . . . . . . . . . . . . . . . 122
5.3 Ear Decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Strong orientations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.4 Directed Ear Decompositions . . . . . . . . . . . . . . . . . . . . . . 129
5.5 Related Reading. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Even Cycle Decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Matroids and Nonseparability . . . . . . . . . . . . . . . . . . . . . . . 133
5.1 Cut Vertices
In Chapter 3, we introduced the notion of a cut edge and discussed various proper-
ties of connected graphs without cut edges. Here, we consider the analogous notion
for vertices. There are, in fact, two closely related notions, that of a cut vertex and
that of a separating vertex.
A cut vertex of a graph G is a vertex v such that c(G−v) > c(G). In particular, a
cut vertex of a connected graph is a vertex whose deletion results in a disconnected
graph. This notion is illustrated in Figure 5.1, the cut vertices being indicated by
solid dots.
By Exercise 3.1.3, a graph is connected if any two of its vertices are connected by
a path. Connected graphs without cut vertices have a stronger property, described
in the theorem below. Two distinct paths are internally disjoint if they have no
internal vertices in common.
Theorem 5.1 A connected graph on three or more vertices has no cut vertices if
and only if any two distinct vertices are connected by two internally disjoint paths.
118 5 Nonseparable Graphs
Fig. 5.1. The cut vertices of a graph
Proof Let G be a connected graph, and let v be a vertex of G. If any two vertices
of G are connected by two internally disjoint paths, any two vertices of G− v are
certainly connected by at least one path, so G− v is connected and v is not a cut
vertex of G. This being so for each vertex v, the graph G has no cut vertices.
Conversely, let G be a connected graph on at least three vertices, with no
cut vertices. Consider any two vertices u and v of G. We prove, by induction on
the distance d(u, v) between u and v, that these vertices are connected by two
internally disjoint paths.
Suppose, first, that u and v are adjacent, and let e be an edge joining them.
Because neither u nor v is a cut vertex, e is not a cut edge (Exercise 5.1.2) and
therefore, by Proposition 3.2, lies in a cycle C of G. It follows that u and v are
connected by the internally disjoint paths uev and C \ e.
Suppose, now, that the theorem holds for any two vertices at distance less than
k, where k ≥ 2, and let d(u, v) = k. Consider a uv-path of length k, and let v′ be
the immediate predecessor of v on this path. Then d(u, v′) = k − 1. According to
the induction hypothesis, u and v′ are connected by two internally disjoint paths,
P ′ and Q′ (see Figure 5.2).
Because G has no cut vertices, G − v′ is connected and therefore contains a
uv-path R′. The path R′ meets P ′ ∪ Q′ at u. Let x be the last vertex of R′ at
which R′ meets P ′ ∪Q′; without loss of generality, we may suppose that x lies on
P ′. Define P := uP ′xR′v and Q := uQ′v′v. Then P and Q are internally disjoint
uv-paths in G. �
P ′
Q′
R′
u v
v′
x
Fig. 5.2. Proof of Theorem 5.1
5.2 Separations and Blocks 119
Generalizations and variants of Theorem 5.1 are discussed in Chapter 7 and
Chapter 9.
Exercises
5.1.1 Show that every nontrivial graph has at least two vertices that are not cut
vertices.
�5.1.2 Let G be a connected graph on at least three vertices, and let e = uv be a
cut edge of G. Show that either u or v is a cut vertex of G.
5.1.3 Let G be a nontrivial connected graph without cut vertices, and let H be
obtained from G by adding a new vertex and joining it to two vertices of G. Show
that H has no cut vertices.
5.1.4 Let G be a nontrivial connected graph without cut vertices, and let X and
Y be two (not necessarily disjoint) sets of vertices of G, each of cardinality at least
two. Show that there are two disjoint (X,Y )-paths in G.
5.1.5 Show that any two longest cycles in a loopless connected graph without cut
vertices have at least two vertices in common.
—————
—————
5.2 Separations and Blocks
Whilst the notion of a cut vertex, as defined in Section 5.1, is the most natural
analogue for vertices of the notion of cut edge, a slightly more general concept is
needed for graphs which may have loops.
A separation of a connected graph is a decomposition of the graph into two
nonempty connected subgraphs which have just one vertex in common. This com-
mon vertex is called a separating vertex of the graph. The separating vertices of
a disconnected graph are defined to be those of its components. A cut vertex is
clearly a separating vertex, but not conversely: a vertex incident with a loop and
at least one other edge is a separating vertex but not necessarily a cut vertex.
However, in a loopless graph, every separating vertex is indeed a cut vertex, so in
this case the two concepts are identical. Whereas the graph shown in Figure 5.1
has four cut vertices, it has five separating vertices, as indicated in Figure 5.3.
Nonseparable Graphs
A graph is nonseparable if it is connected and has no separating vertices; otherwise,
it is separable. Up to isomorphism, there are just two nonseparable graphs on one
vertex, namely K1, and K1 with a loop attached. All nonseparable graphs on two
120 5 Nonseparable Graphs
Fig. 5.3. The separating vertices of a graph
or more vertices are loopless. Multiple edges play no role here: a loopless graph is
nonseparable if and only if its underlying simple graph is nonseparable. Apart from
K1 and K2, the most basic nonseparable graphs are the cycles. Whitney (1932c)
showed that nonseparable connected graphs may be characterized in terms of their
cycles, as follows.
Theorem 5.2 A connected graph is nonseparable if and only if any two of its edges
lie on a common cycle.
Proof If G is separable, it may be decomposed into two nonempty connected
subgraphs, G1 and G2, which have just one vertex v in common. Let ei be an edge
of Gi incident with v, i = 1, 2. If either e1 or e2 is a loop, there is clearly no cycle
including both e1 and e2. If not, v is a cut vertex of G. Let vi be the other end of
ei, i = 1, 2. Then there is no v1v2-path in G− v, hence no cycle in G through both
e1 and e2.
Conversely, suppose that G is nonseparable. Let e1 and e2 be two edges of G.
Subdivide ei by a new vertex vi, i = 1, 2. The resulting graph H is also nonsepa-
rable (Exercise 5.2.1). By Theorem 5.1, there is a cycle in H through v1 and v2,
hence a cycle in G through e1 and e2. �
Blocks
A block of a graph is a subgraph which is nonseparable and is maximal with respect
to this property. A nonseparable graph therefore has just one block, namely the
graph itself. The blocks of a nontrivial tree are the copies of K2 induced by its
edges; and, in general, the blocks of a connected graph fit together in a treelike
structure, as illustrated in Figure 5.4. In order to prove this assertion, we note first
a number of basic facts about blocks.
Proposition 5.3 Let G be a graph. Then:
a) any two blocks of G have at most one vertex in common,
b) the blocks of G form a decomposition of G,
c) each cycle of G is contained in a block of G.
5.2 Separations and Blocks 121
(a) (b)
Fig. 5.4. (a) The blocks of the graph of Figure 5.3, and (b) its block