655 pág.

## 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, ﬁrst, 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 ′. Deﬁne 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 deﬁned 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 deﬁned 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 ﬁve 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 ﬁt together in a treelike structure, as illustrated in Figure 5.4. In order to prove this assertion, we note ﬁrst 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