655 pág.

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

such that G \ e is separable. Show that the block tree of G \ e is a path. (G.A. Dirac; M.D. Plummer) ————— ————— 5.2.12 a) By employing the splitting-oﬀ operation, show that every even graph has an odd number of cycle decompositions. b) Deduce that each edge of an even graph lies in an odd number of cycles. (S. Toida) 5.3 Ear Decompositions Apart from K1 and K2, every nonseparable graph contains a cycle. We describe here a simple recursive procedure for generating any such graph starting with an arbitrary cycle of the graph. Let F be a subgraph of a graph G. An ear of F in G is a nontrivial path in G whose ends lie in F but whose internal vertices do not. Proposition 5.6 Let F be a nontrivial proper subgraph of a nonseparable graph G. Then F has an ear in G. Proof If F is a spanning subgraph of G, the set E(G)\E(F ) is nonempty because, by hypothesis, F is a proper subgraph of G. Any edge in E(G) \ E(F ) is then an ear of F in G. We may suppose, therefore, that F is not spanning. Since G is connected, there is an edge xy of G with x ∈ V (F ) and y ∈ V (G) \ V (F ). Because G is nonseparable, G−x is connected, so there is a (y, F −x)-path Q in G− x. The path P := xyQ is an ear of F . � The proofs of the following proposition is left to the reader (Exercise 5.3.1). Proposition 5.7 Let F be a nonseparable proper subgraph of a graph G, and let P be an ear of F . Then F ∪ P is nonseparable. � A nested sequence of graphs is a sequence (G0, G1, . . . , Gk) of graphs such that Gi ⊂ Gi+1, 0 ≤ i < k. An ear decomposition of a nonseparable graph G is a nested sequence (G0, G1, . . . , Gk) of nonseparable subgraphs of G such that: � G0 is a cycle, � Gi+1 = Gi ∪ Pi, where Pi is an ear of Gi in G, 0 ≤ i < k, � Gk = G. 126 5 Nonseparable Graphs G0 G1 G2 G3 G4 G5 Fig. 5.6. An ear decomposition of the Petersen graph An ear decomposition of the Petersen graph is shown in Figure 5.6, the initial cycle and the ear added at each stage being indicated by heavy lines. Using the fact that every nonseparable graph other than K1 and K2 has a cycle, we may deduce the following theorem from Propositions 5.6 and 5.7. Theorem 5.8 Every nonseparable graph other than K1 and K2 has an ear decom- position. � This recursive description of nonseparable graphs can be used to establish many of their properties by induction. We describe below an interesting application of ear decompositions to a problem of traﬃc ﬂow. Further applications may be found in the exercises at the end of this section. Strong orientations A road network in a city is to be converted into a one-way system, in order that traﬃc may ﬂow as smoothly as possible. How can this be achieved in a satisfactory manner? This problem clearly involves ﬁnding a suitable orientation of the graph representing the road network. Consider, ﬁrst, the graph shown in Figure 5.7a. No matter how this graph is oriented, the resulting digraph will not be strongly connected, so traﬃc will not be able to ﬂow freely through the system, certain locations not being accessible from certain others. On the other hand, the graph of Figure 5.7b has the strong orientation shown in Figure 5.7c (one, moreover, in which each vertex is reachable from each other vertex in at most two steps). Clearly, a necessary condition for a graph to have a strong orientation is that it be free of cut edges. Robbins (1939) showed that this condition is also suﬃcient. The proof makes use of the following easy proposition (Exercise 5.3.9). 5.3 Ear Decompositions 127 (a) (b) (c) Fig. 5.7. (a) A graph with no strong orientation, and (b) a graph with (c) a strong orientation Proposition 5.9 A connected digraph is strongly connected if and only if each of its blocks is strongly connected. � Theorem 5.10 Every connected graph without cut edges has a strong orientation. Proof Let G be a connected graph without cut edges. By Proposition 5.9, it suﬃces to show that each block B of G has a strong orientation. We may assume that B �= K1. Moreover, because G has no cut edges, B �= K2. Thus B contains a cycle and, by Theorem 5.8, has an ear decomposition (G0, G1, . . . , Gk). Consider the orientation of B obtained by orienting G0 as a directed cycle and each ear as a directed path. It can be veriﬁed easily, by induction on i, that the resulting orientation of Gi is strong for each i, 0 ≤ i ≤ k. In particular, the orientation assigned to B = Gk is strong. � Exercises �5.3.1 Deduce Proposition 5.7 from Theorem 5.2. �5.3.2 An edge e of a nonseparable graph G is called deletable if G \ e is non- separable, and contractible if G/e is nonseparable. Show that every edge of a nonseparable graph is either deletable or contractible. 5.3.3 Show that if G has no even cycles, then each block of G is either an odd cycle or a copy of K1 or K2. 5.3.4 Let G be a nonseparable graph, and let x and y be two vertices of G. Show that there is a linear ordering v1, v2, . . . , vn of the vertices of G such that v1 = x, vn = y, and each vertex vj , 2 ≤ j ≤ n − 1, is joined to some vertex vi with i < j and some vertex vk with k > j. 5.3.5 Prove the following dual version of Theorem 5.2: A connected graph is non- separable if and only if any two of its edges are contained in a common bond. 128 5 Nonseparable Graphs 5.3.6 Let G be a graph and let B∼ denote the binary relation on E deﬁned by e B∼ f if and only if either e = f or there is a bond of G containing both e and f . Show that: a) the relation B∼ is an equivalence relation on E, b) the subgraphs of G induced by the equivalence classes under this relation are its nontrivial blocks. 5.3.7 Deduce the result of Exercise 5.1.4 from Theorem 5.8. 5.3.8 Let G be a nonseparable graph diﬀerent from K1 and K2, and let (G0, G1, . . . , Gk) be an ear decomposition of G. a) Show that k = m− n. b) Suppose that Gi+1 = Gi ∪Pi, where Pi is an ear of Gi in Gi+1, 0 ≤ i < k. Set C0 := G0 and, for 1 ≤ i ≤ k, let Ci be a cycle in Gi containing the ear Pi−1. Show that (C0, C1, . . . , Ck) is a basis for C(G), the cycle space of G. �5.3.9 Prove Proposition 5.9. ————— ————— 5.3.10 Let G be a nonseparable nonbipartite graph. a) Show that the cycle space C(G) of G has a basis consisting of m−n even cycles and one odd cycle. b) Deduce that the dimension of the subspace of C(G) generated by the even cycles of G is m− n. (M.A. Henning and C.H.C. Little) 5.3.11 Call a family of subgraphs of a graph linearly independent if the incidence vectors of their edge sets are linearly independent over GF (2). Let G be a nonsep- arable graph on at least two vertices. a) If x and y are two vertices of G, show that there are m − n + 2 linearly independent xy-paths in G, and that this number is the greatest possible. b) Let e be an edge of G. Deduce that the cycle space C(G) of G has a basis consisting entirely of cycles containing the edge e. c) Deduce that G has at least ( m−n+2 2 ) cycles. d) Which nonseparable graphs G have exactly ( m−n+2 2 ) cycles? 5.3.12 Vine A vine on a path xPy in a graph G is a sequence (xiQiyi : 1 ≤ i ≤ r) of internally disjoint ears of P in G such that: x = x1 ≺ x2 ≺ y1 � x3 ≺ y2 � x4 ≺ · · · � xr ≺ yr−1 ≺ yr = y where ≺ is the precedence relation on P (see Figure 5.8). Let xPy be a path in a nonseparable graph G. a) Show that there is vine (xiQiyi : 1 ≤ i ≤ r) on P . 5.4 Directed Ear Decompositions 129 x y P Q1 Q2 Q3 Q4 Q5 Fig. 5.8. A vine on a path b) Set Pi := xiPyi and Ci := Pi ∪ Qi, 1 ≤ i ≤ r. Show that Cjk := �{Ci : j ≤ i ≤ k} is a cycle of G, 1 ≤ j ≤ k ≤ r. c) Suppose that r = 2t− 1 is odd. i) Show that the t2 cycles Cjk, 1 ≤ j ≤ t ≤ k ≤ r, together cover the path P at least t times and each ear Qi min{i, 2t− i} t times. ii) Deduce that if P has length , then one of these cycles has length at least (