On the connectivity of infinite graphs and 2-complexes

DISCRETE MATHEMATICS ELSEVIER Discrete Mathematics 194 (1999) 13-37 On the connectivity of infinite graphs and 2-complexes R. Ayala a'*, M.J. Chfivez b, A, Mfirquez c A. Quintero a a Departamento de Geometrla y Topologia, Facultad de Matem&ticas, Universidad de Sevilla. Apartado 1160, 41080 - Sevilla, Spain b Departamento de Matem6ticas Aplicadas L Escuela de Arquitectura Tkcnica, Universidad de Sevilla. Avda, Reina Mercedes s/n, 41012 - Sevilla, Spain c Departarnento de Matem&ticas Aplicadas I, Facultad de lnform~tica, Universidad de Sevilla, c/Tarfia s/n, 41012 - Sevilla, Spain Received 14 March 1997; revised 5 September 1997; accepted 8 December 1997 Abstract This paper contains a study of the connectivity of infinite graphs and 2-complexes. Various connectivity types are defined and relationships among them are given. In addition new Menger- Whitney type theorems are stated for both graphs and 2-complexes. @ 1999 Elsevier Science B.V. All rights reserved AMS classification: primary 05C40; secondary 57M20 Keywords. Connectivity; End; (Bi)ray; (Locally finite) graph; 2-(bi)ray; (Locally finite) 2-complex O. Introduction Many results concerning the notion of connectivity can be found in graph theory. The classical result on connectivity is the well-known Menger-Whitney Theorem (MWT for short) which shows that for any two vertices of a graph, the maximum number of pairwise disjoint paths joining them is equal to the minimum number of vertices needed to separate them [11,13,9]. A two-dimensional analogue of the MWT for finite 2- complexes is given by Woon in [14], where a 2-path is defined as an ordered sequence, of pairwise adjacent 2-simplices. In addition, Woon posed the question of extending his results to infinite 2-complexes. * Corresponding author. E-mail: quintero@cica,es. 0012-365X/99/$-see front matter (~) 1999 Elsevier Science B.V. All rights reserved PH S0012-365X(98)00033-8 14 R. Ayala et al./ Discrete Mathematics 194 (1999) 13-37 The aim of this paper is to answer Woon's question. We introduce various types of connectivity concerning the ideal points at infinity of an infinite 2-complex K and then we prove several MWT type theorems for such connectivity types. These results are contained in Sections 2 and 3. Incidentally, we provide a more general and shorter proof of Woon's main theorem in Section 2. In pursuing our aim we have found and used several theorems related to already known extensions of the MWT concerning the ideal points at infinity of an infinite graph [12,5,8]. These results seem to be new in the literature and we have included them in Section 1. Finally, in Appendix A, we give several relationships among the different connectivity types introduced in this paper for both graphs and 2-complexes. We next give the basic notation we shall use along this paper. We recall that a simplicial complex, K, is a set of simplices such that: (a) If a E K and ~ is a face of ~r (~ <a, for short) then T E K. (b) If a, a ~ E K then a A & is empty or a common face of a and &. The complex K is locally finite if any a E K is the face of only finitely many simplices of K. For a E K the star of a in K is the subcomplex st(a; K) = (#; ~ E K with # <T and a < z}. The link of a in K is the subcomplex lk(a;K)= {# E st(a;K); a A ~=O}. A subcomplex L of K is a complex whose simplices are simplices of K. Given a subcomplex L c_ K, the notation K\L will stand for the subcomplex of K generated by K-L; that is, K\L= {v E K; r<p and p ~L}. The i-skeleton of K is the subcomplex ski K C K consisting of all simplices a E K with dim a ~< i. We say that K is purely n-dimensional when any simplex a E K is the face of some n-simplex of K. For the sake of simplicity, we shall say that K is an n-complex when K is a purely n-dimensional locally finite connected complex. Let a be an (n - l)-simplex of an n-complex K. The valence of a, val(a), is the number of n-simplices in st(a; K). The valence of K is the number val(K) : min{val(a); dim a = n - 1 }. An (n- 1)-simplex cr E K is said to be a boundary simplex when val(cr)= 1. Otherwise we say that ~r is an interior simplex. The boundary of K, OK, is the smallest subcomplex of K containing the boundary simplices. The boundary OK is said to be full when any simplex in K meets OK in a (possibly empty) face. Given an increasing sequence of finite n-subcomplexes KiCintKi+~ (i~>1) with OG K = Ui~l Ki, a Freudenthal end of K is a decreasing sequence (Ci)i~>l of infinite connected components Ci C_K- Ki (i>>, 1). We recall that there are only finitely many infinite connected components in K- Ki for each i~>l. Let ~(K) be the set of Freudenthal ends of K. It easy to check that ~(K)=o~(sk 1K). Moreover, it can be proved that ~(K) can be topologized in such a way that ~(K) is homeomorphic to a closed subset of the Cantor set. See [4] for more details on the space ~-(K). R. Ayala et al./Discrete Mathematics 194 (1999) 13 37 15 1. Some Menger-Whitney type theorems for infinite graphs For a graph we mean a connected 1-complex G. In particular G will always be locally finite. Let V(G) denote the set of vertices of G. A path ~ : aoan between two vertices a0, an E G is a finite sequence of vertices {a0 ..... an} such that ai ~ aj (i ~ j) and the segment (ai, ai+l) is an edge of G (O<~i<<.n - 1). A path ~ between the sets A,BC_ V(G) is a path c~:ao-an with ~NA={a0} and ~NB---- {an}. A (one-way) ray R : a0 - ec starting at a0 E G is a sequence of vertices {a0 .... } such that ai :~ a/ (i C j) and (ai, ai+l) is an edge of G. A ray between 17 c_ V(G) and infinity (~, for short) is a ray R starting at some eel7, with II•R={e}. It is clear that a ray defines a unique Freudenthal end. Moreover it is not hard to show that the Freudenthal ends of G can be described as equivalence classes of rays, where two rays R and R I are related if there exists a ray R" whose intersections with R and R' are infinite (see [12] for details). A ray R : a0-e between a0 E V(G) and e E Y(G) is a ray starting at a0 which defines the end e. Similarly we can define a ray between the sets 17 C V(G) and F C_ ~(G). Finally, a biray (or two-way ray) with source e and target e/R : e - e/ is a sequence of vertices indexed by the set of integer numbers 7/{... a-2,a-l,a0,al, a2...} such that aiCaj (iCj), the segment (ai, ai+l) is an edge of K, and R defines the ends e.,e' E Y(G). Similarly we can define a biray between F,F'C_ ~(G). Two paths (rays, respectively) ~, fl:a-b (~,/3 :a-oo, resp.) are said to be independent when 7 N/3 = {a, b} (~ n/3 = {a}, resp.). Two birays are independent when they are disjoint. The dual notion to independent paths is the notion of cut-set. When we introduce the ends and the infinity point oo of a graph, different notions of cut-set can be considered. Namely, given a (finite) set of vertices J C V(G) we say that J is a cut-set for a, bE V(G) if a and b lie in different connected components of G- J. Notice that J exists since G is locally finite. Moreover, the set J is a cut-set for a E V(G) and oc if a lies in a finite connected component of G -J. Given a E V(G) and E ~(G) we say that J is a cut-set for a and e when a does not lie in the connected component ~ C_ G - J which defines e. Finally, J is a cut-set of ~,e t E ~-(G) when For the sake of simplicity by a trajectory we shall mean a path, a ray, or a biray accordingly to the context. Various Menger-Whitney type theorems relating the different cut-sets and the corresponding sets of independent trajectories can be found in the literature. In order to deal with them in a simple way we consider the set of symbols {V(G),oo, Y(G)} and we choose the pairs (V(G), V(G)), (V(G),oe), (V(G),Y(G)), and (~-(G),~(G)). Any of these pairs is called a connectivity pair. Given a connectivity pair (A,B) and a E A and b E B with a ~ b, the connectivity order of (a, b) is the maximum number Conn(a, b) of independent trajectories from a to b. The connectivity order of the pair A0 CA, B0 C B is the number Conn(Ao, B0)= min {Conn(a, b); a E Ao, b E B0, a ¢ b}. The connectivity order of type (A, B) of G is the 16 1~ Ayala et al./Discrete Mathematics 194 (1999) 13-37 number Conn(A,B). We say that G is n-connected of type (A,B) if Conn(A,B)>~n. Notice that for one-ended graphs only the connectivity orders of type (V(G), V(G) and (V(G), oo)) = (V(G), ~(G)) are defined. For the connectivity pair (A,B), let 6P(A,B) denote the family of all cut-sets of type (A,B), i.e. 5P(A,B)= U{Se(a,b); aEA, bEB, a¢b} where 5e(a,b) is the family of all the cut-sets for a, b in G. Moreover, the cut-order of (a, b) is the number Sep(a,b) =min{[J[; J E 6e(a,b)}. Here IJI denotes the cardinal number of J. Notice that these numbers are finite since G is locally finite. Then the following general form of the Menger-Whitney theorem holds. Indeed for the pairs (V(G), V(G)), (V(G), oo), (V(G), ~-(G)), and (~(G), ~(G)) the corresponding proofs can be found in [9, 7, 8,12] respectively. Theorem 1.1. For any connectivity pair (A,B) and a E A, b E B with a ~ b, Sep(a, b)= Conn(a,b). In particular, the connectivity order Conn(A0,B0) coincides with the cutorder Sep(Ao, Bo) -- min{ [J I; J E 5P(a, b); a E Ao, b E Bo; a 5~ b} for any pair Ao C A and Bo C_ B. In order to keep this section within a sensible length we shall give the relationships among the different connectivity types in Appendix A. We now proceed to give some consequences and variations of the Menger-Whitney theorem stated above for the various connectivity types defined here. They are the analogues of already known results involving the connectivity type (V(G), V(G)) and the classical Menger-Whitney theorem. For the connectivity type (V(G),oo) we can prove the following theorems Theorem 1.2 (Dirac [3, Theorem B]). Let G be an infinite graph, then the following statements are equivalent: (a) G is n-connected of type (V(G),oo). (b) Let A = {vl,..., Vp} be a finite set of vertices of G. Given any family {al ..... ap} of positive integers with ~P=~ ai = n there exist n independent rays from A to oo such that ai of them start from vi, for all i. (c) Given any set of vertices A C V(G) with [A[ = n there exists a family of n disjoint rays from A to c~. Proof. (a) =~ (b): It is a particular case of Proposition 1.7 below; see Remark 1.8. (b) =~ (c): It is obvious. (c) ~ (a): Clearly, condition (c) implies that val(G)~>n. Otherwise, if v E V(G) is a vertex with val(v)~<n- 1, we can form a set A C_ V(G) containing {v} Ulk(v; G) with [A[ =n and (c) does not hold for A. As val(G)~>n, then Ilk(v; G)[ ~>n for all v E V(G), and by condition (c) we can find n disjoint rays starting at n vertices in lk(v; G), and these rays yield n independent rays starting at v. This finishes the proof. [] R. Ayala et aL/Discrete Mathematics 194 (1999) 13-37 17 Theorem 1.3 (Linck [10]). Let G be an infinite graph. Then the following statements are equivalent: (a) G is n-connected of type (V(G),cxD). (b) Given a set AC_ V(G) with IAI--n- 1, for any vertex yEA there exists a birav RCG with RNA={v}. (c) Given a set B c V(G) with IBI = n, for any vertex v E B there exists a ray R c_ G with Rn~= {v}. Proof. (a)~(b): Given AC_ V(G) with [Al=n- 1, we take yEA. Since G is nconnected of type (V(G),oo) we can find n independent rays starting at v. Hence at least two rays do not contain vertices in A other than v. These two rays define a biray R with R NA = {v}. (b) ~ (c): There exists a biray R which contains v and at most a vertex v~ E B. Then it is clear that we can find a ray R~C_ R containing v with R~N B = 0. (c) ~ (a): Let J C V(G) be any set of vertices with IJI ~<n- 1, Given any vertex v E G-J, by using (c) we can find a ray R C G such that v E R and R nJ : 1~. Therefore, the connected component of v in G-J is infinite, and Jf~A~(V(G),oc). [] Theorem 1.4 (Dirac [2] and Halin [6]). Let G be an infinite s-connected 9raph. Then the following statements are equivalent: (a) G is n-connected of type (V(G),cx~). (b) For A = {vl,...,Vn--1} ~ V(G) and 1 ~<m~<min{s + 1,n - 1} there exists a biray R C G with R NA = {vl ..... Vm}. (c) For B= {vl ..... vn} C_ V(G) and 1 ~<m~<min{s ÷ 1,n} there exists a ray R C_ G with R NA = {Vl ..... vm}. Proof. (a) ~ (b) The case m --- 1 is Theorem 1.3. Assume we have already proved (b) for m<<,k - 1 <<,s. Let R be a biray with RNA = {vl ..... Vk-1}. Given vk EA, by using Theorem 1.2b we can find k+ 1 independent rays L~ ..... L~+j from vk to oc which do not meet {vk+l ..... v,-1}. When RNLi 7&0, let ai E V(Li) denote the first vertex in R (l<~i~<k+ 1). The vertices vl ..... vk-1 define a decomposition of R into k- 2 paths R1 ..... Rk-2 and two rays R_~, R~. Assume that two vertices as, at lie in the same path (ray) Rj (l<~j<~k- 2, j= + cx~). Then a biray can be found in RUL~.ULIt containing {vl ..... vk}. Here L~ C_Li denotes the path from vk to ai. Therefore, we can now assume that at least one ray Li does not meet R. In case that only Ll misses R, we can assume that each ai (2<~i<~k + 1) defines a unique path or ray Rj(i) (1 <~j(i)<~k -2, j(i)= 4-~). Hence, a suitable biray can be found in R U L1 U LI 0 where j(io)= 4-~. At this point it will suffice to assume that at least two rays Li miss R. As G is s-connected we can also find a set of s independent paths 7j:vk - vj (j¢k). Let biE~'i (l<~i<~k- 1) denote the first vertex in 7inR. If no b~ lies in R_~ URn, there must exist a path R/ containing two vertices bp, bq and hence a biray 18 R. Ayala et al./Discrete Mathematics 194 (1999) 13-37 R'CRUVpUTq can be easily found with {vl ..... vk}CR'. Here 7pC),p denotes the path from v~ to bp. Assume now bl ERos. As there are two rays Lp,Lq which are disjoint with R, we can assume without loss of generality that Lp AVl = {vk}, and it is clear that a biray can be found in RULp UTl containing {vl ..... vk}. The proof of (a)=:> (c) is similar and we omit it. Moreover, (b)~ (a) as well as (c) ~ (a) follow from Theorem 1.3. [] Example 1.5. Any infinite tree G with all vertices of valence n~>4 shows that Theorem 1.4 does not hold without the hypothesis on the connectivity of G. Indeed, G is 1-connected of type (V(G),V(G)) but n-connected of type (V(G),oo). Moreover, G does not satisfy either (b) or (c) in Theorem 1.4 for m : 2. We next give similar theorems for the connectivity type (V(G),~(G)). We start with the following characterization Theorem 1.6 (Dirac [3, Theorem B]). Let G be an infinite 9raph, then the follow& 9 statements are equivalent: (a) G is n-connected of type (V(G),~(G)). (b) Given two sets A = {vl ..... Vp} C_ V(G) and B = {el ..... ~q} C_ ~(G) and two sets of positive integers {al ..... ap} and {b~ ..... bq} with ~-~f=lak= ~-~qh=~bh=n, there exist n independent rays from A to B such that ak of them start at vk and bh of them define eh for all k, h. Theorem 1.6 is an immediate consequence of the following more general proposition which will be used also for 2-complexes in Section 3 below. Proposition 1.7. Let G be an infinite 9raph A = {Vl ..... Vp} C V(G), and M = {BI ..... Bq} a family of pairwise disjoint closed sets of Freudenthal ends of G. Assume that for each pair (k,h) there exist n rays running from vk to Bh. Then 9iven two sets of positive integers {al ..... ap} and {bl .... , bq} with ~-~Pl ak = ~-~q=l bh = n, there exist n independent rays from A to [-Jq=l Bh such that ak of them start at vk and bh of them end at B h for all k, h. Proof. First we consider a family ~(k,h) of n pairwise disjoint rays from vk to Bh and let ~(k,h)C_Bh denote the set of ends defined by the rays in ~(k,h). Then we choose a connected finite subgraph K C G such that st@k; G)CK for all vk EA and moreover the connected components V~ C_ G-K determined by the ends e c U {~(k, h); 1 ~<k ~< p, 1 ~<h ~<q} are pairwise disjoint in such a way that the rays in :~ = [_J {~(k, h); 1 <~k<<.p, 1 <~h<~q} which meet V~ are exactly those determining e. Furthermore, for each R E ~(k,h) with end e E ~(k,h) let TR C R N V~ be a subray of R. Given eE~(k,h) we form the family ~Y'-~. consisting of all rays TR where RE~, and o~(R)= e and we choose a subfamily J/g~ _C ~ such that [J/~[ = max{[~vg~[; ~,~ C_ ~ and the rays in ~ are pairwise disjoint}. R. Ayala et al./Discrete Mathematics 194 (1999) 13~7 19 Next for each R E ~ with ~(R) = e and TR ~ ~/,: we choose n pairwise disjoint paths in V~ joining R to all rays in J/0. We call them the net of R and we denote it by ~.4~. Notice that some paths in JV8 may be degenerate one-point paths. We take a new finite subgraph G~c_ G containing K, all paths in the net ~.~ of each R, and moreover a subpath in each R (in J//~ or not) passing through all points in R obtained as intersection of R with the paths in the nets. Furthermore, we require that each T E Jt'~; meets the frontier Fr(G') = G ~ N (G\G') in just one vertex. Here G\G' is the subgraph generated by G - G', see Introduction. Then for each k and h we consider the sets of vertices Fk=lk(vk;G)- A and Oh=Fr(G')N(U{T; TEJCI~ and eEB~}). Notice that Fk ¢i~ for all k since p<~n. We now construct a new graph Go as follows. We take pairwise disjoint sets {Dk}l<~k<~p and {Eh}l<~h<~q with IDkl=a~ and LEhl=bh. Then we form the complete bipartite graphs Lk =K(Dk,Fk) and L~ =K(Eh, Oh). Finally, we consider two further vertices c and c ~ and the complete bipartite graphs C=K(c, UP l Dk) and C'=K(c',Uq j Eh) and we set Go= (G'~C_LJst(vk;G))U (kO1Lk)U (j~,L~)UCUC'. We claim that Conn(c,c')>~n in Go. Indeed, let JCGo be a set of vertices with [JI ~<n- 1. Then one finds x0 EDko -J and Y0 EEho -J for some k0 and h0. Moreover, there exists at least one ray R E ~(k0, h0) which does not meet J. However, R may contain some other vertices vj E A-{vk0 }. We proceed to show that it is always possible to choose R in such a way that for any vj E A A R we have Di -J 7 ~ f). Otherwise, all rays in ~(ko, ho) which avoid JNG=J71G' contain some viEA with D/C_J. Let I = {k;D~ c J}. Then one gets necessarily n = I~(k0,h0)[ <~ [J N G U {vk; k EI}[. Moreover, since Dk C__ J for all k E I one gets also IJ N G] ~<n - 1 - ~kc~ ak. This leads to the contradiction n ~< [J A G[ + 1I[ ~<n - 1. Therefore, we have proved the existence of a non-empty subset 5a(k0, h0) C ~(k0, h0 ) consisting of rays R which do not meet J and for all vj ERNA we have Di-J 7~ ~. We consider the family of ends C~(ko, ho) = {e ~_ Y(k0,h0); e = ,~-(R) with R E Lf(k0,h0)}. We call an end in W(k0, h0) a clean end. We next show that there exists a clean end e0 such that some To E J/~:,, does not meet J. Otherwise, if m,: = [.//g~.[ and I = {k;D~ C J} we have we have m~<~(n-1)- ~ak-r, ~C6(ko,ho ) k~l where r= [J - U~.E~(k~,h0) ~[. In addition, if w,: is the number of rays in :~(ko, ho) which defines the end e, the maximality of ~¢/~: and the above inequality yield w,: <~ ~-~ ( ko, ho )rn~ <. ( n -1) - ~ w~:, ~:~'(ko, ho ) ~c~ ~/G~-(ko, ho) ~ (k~l,ho) since ~e,E,N(ko,ho)_~g;(ko,ho) W e, <<.r + III. Hence n = ~.~(~o,ho) w,: ~<n -- 1 which is a contradiction. 20 R. Ayala et al./Discrete Mathematics 194 (1999) 13-37 Therefore, we have proved that there exists eoECg(ko, ho) and ToEJ//~o with To A J = 0. Hence, there exists a ray Ro E La(k0, h0) with if(R0)= e0. In addition, the construction of the graph G p allows us to choose a path 70 c G ~ from R0 to To such that the union U=7oURoUTo misses the set J. Moreover, Afq(ToMT0)=0 and if (A - {Vko}) NRo ¢ ~ we can replace Vko by the last vertex in R0 NA since Dj - J ¢ 0 for all vj E Ro A A. For this we use that R0 E 5¢(k0, ho). So, we can assume, without loss of generality, that UAA={vko} and then we easily connect c to c' in Go by a path passing through x0, U, and yo. We have checked that Conn(c,c~)>>.n in Go and the Menger-Whitney theorem for the connectivity pair V(G), V(G) in (1.1) provides n independent paths 71,72 ..... 7n in Go from c to c ~. In particular, ),jfq G ~ (1 <<.j<~n) are pairwise disjoint paths with 7j M G' running from some I'k(j) to some Oh(j). Moreover, for each k and h only ak and bh, respectively, of the paths 7j M G t verify k(j)=k and h(j)=h, respectively. Now it is clear that {7j M G~}I <~j<~n can be extended to a family of n independent rays with the required properties. This finishes the proof. [] Remark 1.8. Since a ray starting at v is just a ray running from v to if(G), one gets (a) =~ (b) in Theorem 1.2 as a particular case of Proposition 1.7 by setting q = 1 and B~ = if(G). Other results concerning the connectivity pair (V(G), ~(G)) are the following. Theorem 1.9 (Linck [10]). Let G be an infinite graph. Then the following statements are equivalent: (a) G is n-connected of type (V(G),~(G)). (b) Given AC_ V(G) with [A[=n - 1, for any vertex yEA and any end eEl(G) there exists a biray R C G with both ends ~ and R MA----{v}. (c) Given a set BC V(G) with IBI =n, for any vertex vcB and any end ~E~-(G) there exists a ray RC G whose end is ~ and such that RMB= {v}. The proof of Theorem 1.9 follows the same pattern as the proof of Theorem 1.3 and we omit it. Moreover, since Conn(V(G),~(G))= Conn(V(G), V(G)) (see Proposition A.2) we get the following analogue of the (1.4) above Theorem 1.10 (Dirac [2] and Halin [6]). Let G be an infinite graph. Then the following statements are equivalent: (a) G is n-connected of type (V(G),~(G)). (b) For A={Vl ..... vn_l} C_ V(G), eEJ~(G), and l <~m<~n- 1 there exists a biray R whose only end is ~ and such that R NA ~- {vl ... Vm}. (c) For B={vl ..... vn} C_ V(G), eEl(G), and l <<.m<<.n there exists a ray R whose only end is ~ and such that R NA = {vl ..... Vm}. The proof is similar to the proof of Theorem 1.4. We leave it to the reader. R. Ayala et aL /Discrete Mathematics 194 (1999) 13 37 21 Theorem 1.11. Let G be an infinite graph. Then the following statements are equivalent (n>~2 and I~(G)I >_-2): (a) G is n-connected of type (V(G),~.~(G)). (b) For A = {vt ..... v,_t} C V(G), e, d E ~(G), and 1 ~m<~n- 1 there exists a biray R whose ends are e and d and such that RNA = {Vl ..... Vm}. Proof. (a)~(b): By using (a) we can find two rays R1,R2 from vl to e, such that RinA={vl} (i= 1,2). Similarly there are two rays R~ (j= 1,2) from vl to d with the same property. As e # d each intersection R~ n Rj is finite. It is now easy to construct a biray R C_RI UR2 UR'~ UR~ with J~(R)= {~,d} and RNA = {v~}. Hence, we have shown (b) for m = 1. At this point we can follow the pattern of the proof of Theorem 1.4 to prove (b). The converse (b)~ (a) follows from Theorem 1.9, [] For the connectivity pair (~-(G),~(G)) we can prove an analogue of Theorem 1.6. Actually we shall use Proposition 1.7 to prove a more general result. Namely Proposition 1.12. Let G be an infinite graph and ~¢ = {Al ..... Ap} and ~ = {Bt ..... Bq} two families of closed sets of Freudenthal ends of G such that the elements of ~4UM are pairwise disjoint. Assume that for each pair (k,h) there exist n birays running from Ak to Bh. Then given two sets of positive integers {al ..... ap} and {bl ..... bq} with ~'~;-1 ak = ~-~q=l bh =n, there exist n independent birays from P A uq_l Bh such that ak of them start at Ak and bh of them end at B~ [br Uk=l k to all k, h. Proof. First for each pair (k,h) we choose a family ~(k,h) of n pairwise disjoint birays from Ak to Bh. Let ~.~(k,h)- C_Ak and ~(k,h) + C_Bh denote the sets of left and right ends, respectively, defined by the birays in ~(k, h). Then we consider a connected finite subgraph K C_ G such that the connected components V~ c_ G - K defined by the ends c~E Uk.~(Y(k,h)-U~(k,h) +) are pairwise disjoint. Moreover, we also assume that the rays which meet V~ are exactly those birays determining a. Then if R E ~(k, h) defines the left end t/, let TR C R n V~ be a subray of R contained in the component Vq. Given the left end q E ~(k,h)- we form the family Y, consisting of all rays TR with R E U{~(k, h); 1 ~<k ~< p, 1 ~< h ~< q} and such that t/is the left end of R. Then we choose a maximal subfamily J/n C_ 3-'~ as in the proof of (1.7) as well as nets of paths ,A~ from all R ~ J/~ to the rays in #/,l" We now extend the infinite subgraph K U {~;~ E Uk, hff(k,h) +} to a new graph G' by adding finite subgraphs in each V, with r/E Uk, h~(k,h)- in such a way that G' contains all paths in the net JVR of each R as well as a subray in R passing through all points obtained as intersection of R with the paths in J VR. Furthermore, we require that for every left end r/ each ray T E ~/~ meets the frontier Fr(G~) = G t N(G\G ~) in just one vertex. Then for each k we consider the set of vertices Fk=Fr(G')N(U{T; T E J/ln and t/CA~}). We now construct a new graph Go as follows. We take pairwise disjoint sets {Dk}l<,k<~p with [Dk[ =ak. Then we form 28 R. dyala et al./Discrete Mathematics 194 (1999) 13-37 Proof. By using the same arguments as in the proof of Proposition 2.12 we find n independent birays from i,l(h(H)) to i,I(F). These birays define n independent 2-birays in P joining H to F. [] The previous propositions from Propositions 2.11 to 2.13 can be summarized in the following general Menger-Whitney Theorem for admissible 2-complexes: Theorem 2.14. Let P be an admissible 2-complex P. For any connectivity pair (A,B), if a E A, b E B and a ~ b then Sep(a, b) = Conn(a, b ). In particular, the connectivity order of type (A, B) coincides with the cut-order Sep(A, B) = min{Sep(a, b); a E A, b E B; a ~ b). Notice that these numbers are finite since P is locally finite. We finish this section with a theorem which allows us to consider cut-sets containing only edges for any type of connectivity. This theorem was originally proved by Woon [14, Theorem 3] for finite 2-complexes and connectivity pair (g(P),g(P)). We give here a more general and simpler proof. Theorem 2.15. Let P be an infinite admissible 2-complex such that val(e)>>.n for any interior edoe e E g(P). Then P is n-connected of type (A,B) if and only if there exists no cut-set J E 5a(A,B) N ~(P) with IJ[ <n. Theorem 2.15 is an immediate consequence of the following Lemma 2.16. If J is a minimal cut-set of type (A,B)for P with IJl=k <n, then there exists a cut-set J' E 6~(A,B) M ~(e(P)) with IJ'I -- k. Proof. We shall prove the lemma inductively on the number m >~ 0 of triangles in J. The case m = 0 is trivial. Assume that the result holds for m, and let J = {t, tl, t2 ..... tm} U {am+l ..... ak-1 } be a cut-set of type (A,B) with triangles t, tl, t2 ..... t,n. Given c E C, for any C E {8(P), oo, ~(P), ~,~2(P)}, let Ac denote the set consisting of all edges in P which can be joined to c by trajectories which do not meet J. If J is a cut-set for a E A and b E B we have Aa M Ab-----0. Moreover, since J is minimal there exists a set {7~}~ 6 J of independent trajectories with 7~ A J = {~} for each ~ E J. Given 7t, let ea (eb respectively) denote the edge of t which appears in Aa f-17t (Ab A ~)t respectively). Finally, let e be the third edge of t. Assume A,B = 8(P). Case 1: AeAAa=O. If ea=a, as val(a)~>n there exist p triangles sl ..... Sp in st(a;P)-J. Moreover, since p>km- 1 there exists an edge d<sj with at~J. Thus a t E Aa, and any 2-path from a t to b must meet J. Furthermore, the assumption Ae nAa = 0 yields that any 2-path ~ :a'-b with ¢ NJ = {t} must contain a. Therefore J1 = {a, tl ..... tm}U {am+l ..... ak--l} is a cut-set for a t and b with only m triangles. R. Ayala et al./Discrete Mathematics 194 (1999) 13-37 29 If a#e,, the assumption AenAa=O implies that J1 ={ea, tl ..... tm}U{am+l ..... ak-l} is a cut-set for a and b. Case 2: AenAa#O. As AanAb=O, it follows that AeNAb=q), and we proceed in the same way by replacing a by b. Assume A = g(P), and B # 8(P). In Case 1, the proof is the same as above. In Case 2, the set J2={eb, h ..... tm}U{am+l .... ,ak-I} is a cut-set for a,b with m triangles. Finally, assume A,BE{~2(P),:~(P)}. In Case 1 the set J3={ea, tt,...,tm}U {am+l ..... ak-l} is a cut-set for a,b. In Case 2 the set ./2 above is a cut-set. We now apply the induction hypothesis to finish the proof. [] 3. Some Menger-Whitney type theorems for 2-complexes This section contains the two-dimensional analogues of the results stated at the end of Section 1. We recall that the analogues for (g(P),8(P))-connectivity are given in [14, Section 4] for finite 2-complexes. Actually, the same proofs work for infinite 2-complexes. We shall start with the following theorems concerning the connectivity type (g(P), o~). Theorem 3.1. Let P be an admissible infinite 2-complex with val(P)~>n, then the following statements are equivalent: (a) P is n-connected of type (8(P), oo). (b) Given A = {el ..... ep} C_ g(p) and any family {al ..... ap} of positive inteyers with ~~P- 1 ai =- n there exist n independent 2-rays from A to oo such that ai of them start from ei, for all i. (c) Given any set of edges A C 8(P) with IAI--n there exists a family of n independent 2-rays from A to oe. Proof. (a)~(b): According to Proposition 2.9 Conn(E,~)=n for the set E of vertices of G(P) associated to interior edges. Moreover, the set A yields a set ,4={~l,...,~n}CE and Proposition 1.7 applied to G(P) (see Remark 1.8) shows that there exist n rays in G(P) ai of them starting at el. Clearly these rays defined the required 2-rays in P. (b) ~ (c): It is obvious. (c)~(a): Let J be a cut-set for P. As val(P)~>n we can assume that JC_g(p) by Theorem 2.15. If IJ[<<,n- 1 and eES(P)-J we can apply (c) to JU{e} to get a 2-ray R from e to ~ with RNJ=0 which is a contradiction. So IJl>>,n, and P is n-connected of type (8(P), oo). [] Theorem 3.2. Let P be an admissible infinite 2-complex with val(P)>~n. Then the following statements are equivalent: 30 R. Ayala et al./ Discrete Mathematics 194 (1999) 1307 (a) P is n-connected of type (8(P), oo). (b) Given a set AC_g(P) with [Al=n - 1, any edge eEA is contained in a 2-biray which avoids the other n- 2 edges of A. (c) Given a set B C_ g(P) with [B] = n, any edge in B is contained in a 2-ray which avoids the other n - 1 edges of B. Proof. (a)~ (b): By using Proposition 2.9 we get Conn(E, cx~)= n in the the bipartite graph G(P). Here E is the set of vertices of G(P) corresponding to interior edges. Moreover, the set A defines a set A _C E. The same proof as in (a) ~ (b) of Theorem 1.3 yields a biray R in G(P) which contains a vertex ~E-~ and avoids the rest of vertices of _~. The biray R clearly defines a 2-biray in P with the required properties. (b) =~ (c): It is obvious. (c) =~ (a): It is similar to the proof of (c) =¢, (a) in Theorem 1.3. [] Theorem 3.3. Let P be an admissible infinite 2-complex. Assume that P is s-con- nected of type (g(P),8(P)) and val(P)~>n. Then the following statements are equivalent: (a) P is n-connected of type (8(P), oo). (b) For A ---- {el .... ,en-1} C 8(P ) and 1 <<,m <~ min{s+ 1,n - 1} there exists a 2-biray R C P with RNA = {el ..... era}. (c) For A = {el ..... en} C 8(P) and 1 <~m <<. min{s + 1, n} there exists a 2-ray R c p with RNA = {el,...,em}. Proof. (a)~ (b): We know by Proposition 2.9 that Corm(E,c~)=n and Conn(E,E) = s for the set E of vertices of G(P) corresponding to interior edges of P. Moreover, the set A defines a set ,4= {~1 ..... es+l} C E and the inductive proof of (a)~ (b) in Theorem 1.4 can be carried out here to obtain a biray R in G(P) with RNA= {el ..... ~m}- The biray R yields the required 2-biray in P. The proof of (a)~ (c) is similar and we omit it. Moreover (b)~ (a) as well as (c) :=> (a) follow from Theorem 3.2. [] For the connectivity type Conn(g(P),~2(P)) we have the following result which follows the pattern of Theorem 3.2. We leave the proof to the reader. Notice that ~2(P)) is identified with ~(G(P)) by Proposition 2.4. Compare with Theorem 1.9. Theorem 3.4. Let P be an admissible infinite 2-complex with val(P)~>n. Then the following statements are equivalent: (a) P is n-connected of type (g(P), ~,~2(P)). (b) Given a set A C g(P) with [A[ = n - 1, for any edge e EA and any end 6 E ~2(P) there is a 2-biray R with both 2-ends A and such that RNA = {e}. (c) Given a set B C ~(P) with IBI = n, any e E B and any 2-end A there is a 2-ray R whose 2-end is A and such that B N R = {e}. R. Ayala et al./Discrete Mathematics 194 (1999) 13-37 31 Since Conn(g(P), ff2(P))= Conn(g(P), 8(P)), we also get the following theorem. Theorem 3.5. Let P be an admissible infinite 2-complex with val(P)>~n. Then the followin9 statements are equivalent: (a) P is n-connected of type Conn(g(P), ~2(P)). (b) For A = {el ..... e,-l } C_ g(p), A E .~-2(P), and 1 <~m<<.n - 1 there exists a 2-biray R whose only 2-end is A and such that R NA = {el ..... em}. (c) For B = {el ..... e,} C_ g(P), A E ~2(P), and 1 <<.m<~n there exists a 2-ray R whose 2-end is A and such that RNB = {el ..... era}. Proof. We know by Theorem 2.9 that Conn(E,~(G(P))= Conn(E,E)=n. Now we can argue as in Theorem 3.3 to show that (a) implies both (b) and (c). The converses follow from Theorem 3.4. Another result for the same connectivity type is the following theorem (compare Theorem 1.11) whose proof is also omitted. Theorem 3.6. Let P be an admissible infinite 2-complex with val(P)>~n and 1~-2(P)I/>2. Then the followin9 statements are equivalent: (a) P is n-connected of type Conn(8(P), ~-2(P)). (b) For A={el ..... e,_l}Cg(P), A,A' c o~2(P), and l <~m<~n - 1 there exists a 2-biray R with 2-ends A,A ~ and such that RNA= {el ..... em}. For the connectivity type (ff2(P),ff2(P)) we can prove the two-dimensional analogue of (1.6) by applying (1.6) to the bipartite graph G(P) of P. We leave the details to the reader. We finish this section by considering connectivity types of a 2-complex P involving Freudenthal ends. In general there is no bijection between the Freudenthal end of P and the Freudenthal ends of G(P). However, the analogues of Theorems 3.2 and 3.3 for the connectivity pair Conn(g(P),~(P)) hold. We leave to the reader the task of state and prove them. Next example shows that the hypothesis on the connectivity type (g(P), g(P)) is necessary for the analogue of Theorem 3.3. Example 3.7. Let M be any admissible 2-complex which is 3-connected of type (g(P), g(P)) and with only one 2-end (e.g. the 2-skeleton of any one-ended open 3-manifold. See Corollary 2.7, and [1]). Let A = (x0 ..... x ..... } be any sequence of non-adjacent vertices of M. We consider three disjoint copies A i = (x/} CM/ (1 ~<i~<3) of A and M respectively and we construct the 2-complex P0 by identifying to a point y, i for each n. Given y0 c P0 we take three edges adjacent to y0, the three points x n 7i = (yO, Vi)cmi C Po, one in each copy Mi of M. Let c ~P0 and we consider the complex K0 with three triangles (c, yo, vi) (1~<i~<3). We take P=KoUPo. Then P has only one Freudenthal end but three 2-ends. Moreover, P is 3-connected of type 32 R. Ayala et al./Discrete Mathematics 194 (1999) 13-37 (8(P), ~,~(P)) and only 1-connected of type (o~(P), g(P)). Clearly, P satisfies condition (a) but not condition (b) in the analogue of Theorem 3.3. A similar example can be constructed for condition (c). For Freudenthal ends the two-dimensional analogue of Theorem 1.13 also holds. More explictly, we have Theorem 3.8. Let P be an admissible infinite 2-complex; then the following statements are equivalent: (a) P is n-connected of type (~(P), ~(P)). (b) Given any two disjoint sets of Freudenthal ends F = {~h ..... ~/q} and F' = {el .... , ep} and two sets of positive integers {al,...,ap} and {d 1 ..... aq} with ~-~f=l ai = ~-'~qi=l a~. = n, there exist n independent 2-birays from F to F' such that ai of them define ~i and a~ of them define tj, for all i, j. Proof. Clearly only (a) ~ (b) needs to be checked. For this we observe that according to Proposition 2.4 each Freudenthal end ~E~-(P) defines a closed set A~ =i,1(~)C ~(G(P)) where G(P) is the bipartite graph of P. Therefore the sets F and F' determine two families ~'F and dE, of pairwise disjoint closed sets of Freudenthal ends of G(P). As P is n-connected of type (~(P),~(P)) it follows that Proposition 1.12 can be applied to dF and dF, in G(P) to show the existence of n disjoint birays in G(P) such that ai of them start at A~, and bj of them end at A~j. Moreover birays in G(P) can be regarded as 2-birays in P via the bijection g in Proposition 2.4 and now the diagram in Proposition 2.4 yields the result. [] Remark 3.9. We leave to the reader the statements and the proofs of the corresponding theorems for the connectivity pairs (g(P),~(P)) and (~(P),~,~2(P)) by using Propositions 1.7 and 1.12, respectively. Appendix. Some relationships among the various connectivity types Here we give some relationships among the various connectivity orders already defined for graphs and 2-complexes in Sections 1 and 2, respectively. In this appendix we shall use the identity Sep(A,B)=Conn(A,B) provided by Theorems 1.1 and 2.14 without any further comment. We shall start with the results concerning graphs. Lemma A.1. For a graph G the followin9 equalities hold: (a) 50(V(G), V(G)) = 6¢(V(G), ~(G)). (b) /f [~-(G)[~>2 then 6¢(V(G),c~)t_36¢(~(G),~(G))=~Sa(V(G),~(G)). Proof. (a) Let J E Sa(V(G), V(G)) be a cut-set for the vertices v,w E G. Let C~ and Cw be the connected components of v, and w in G-J. If both Cv and Cw are finite there R. Ayala et al./Discrete Mathematics 194 (1999) 13-37 33 must exist a third infinite connected component Coo since J is finite. Then J separates v and w of any end e defined by C~, and so J E 6¢(V(G), Y(G)). If Cv (Cw) is infinite we proceed in the same way with Cw = C~ (C~, = C~, respectively). We have shown ~(V(G), V(G)) C_ 5P(V(G),~(G)). Conversely, ifJ separates v E V(G) of e E ~(G), it is obvious that J separates v of any vertex w E V~. (b) If J E 6~(~(G),J~(G)) then J separates two ends e,e~E ~(G), and therefore it separates ~ from any vertex in the connected component V,; C_ G- J which defines d. Hence, 6P(~-(G), W(G)) C_ ~(V(G), ~(G)). Moreover, if L E 6e(V(G), cxD) then J leaves some vertex v in a finite connected component C~, C_ G - L. Therefore, L separates v from the whole set ~(G), and so L E 6~(V(G),~(G)). Now if K E :T(V(G),~(G))- 6e(~(G),~(G)), K separates an end e E J~(G) of a vertex v E V(G) but the connected component C~, c_ G - K which contains v must be finite. Therefore K E.~(V(G),o~). Hence, equality (b) holds. [] Proposition A.2. (a) Conn(V(G), V(G)) = Conn(V(G), ~(G)) <~Conn(J~(G), ~(G)). (b) Conn(V(G), ~(G)) ~< Conn(VG), cx~ ). (c) In fact, when [~(G)L >/2 we have Conn(V(G), ~(G)) -- min{Conn(V(G), oo), Conn(~(G), ~(G))}. Corollary A.3. Conn(V(G), V ( G ) ) = Conn(V(G), ~,~ ( G ) ) is the smallest connectivity order of G. Moreover, for a one-ended graph the connectivity order Conn(~-(G), ~(G)) is not defined and the other connectivity orders are the same. Proof of Proposition A.2. The parts (a) and (b) are direct consequences of Lemma A. 1. (c) Assume Sep(Y(G), ~(G)) = n < Sep(~(G), ~(G)). Then any J E 5a(V(G), ~(G)) with IJl=n does not belong to ~9~(~(G),~-(G)) and so JE6~(V(G),ac) by Lemma A.l(b). Hence Sep(V(G), c~)~<n, and by (b) we get Sep(V(G), c~)--n. If Sep(V(G), ~(G)) = n < Sep(V(G), co), clearly J ~ Sep(V(G), cx~) when IJI = n. Therefore J E ~9~(~(G), ~(G)) by Lemma A.l(b) and so Conn(~(G), ~(G))~<n, and (a) yields Conn(~(G), ~(G)) = n. [] The width of the end ~, w(e), is the maximum number of pairwise disjoint rays which define e. The number w(e) is attained [7], and it is also called multiplicity in [12]. The width of ~(G) is the number w(G)=min{w(e); e E ~(G)}. We can add to Proposition A.2 the following proposition whose proof is immediate. Proposition A.4. If w(G) and val(G) are the width and valence of G, respectively, then Conn(J~(G), ~(G)) <<.w(G) and Conn(g(G), cxz) ~<val(G). 34 1L Ayala et al./Discrete Mathematics 194 (1999) 13-37 Remarks. A.5. (1) The simple examples below show that the Propositions A.2 and A.4 can be strict. (a) c--i: \1 / inequalites in Conn(V(G),~(G))=2 < Conn(~-(G),~(G))= 3 < w(G)= 4. (b) G= • . , (~'y~-~.. M_..I_.,/M...I._.JM...L_J Conn(V(G),,~(G))= 1 < Conn(V(G),oo) = 2 < val(G) = 3. (2) Notice that for fixed values val(G) and [~(G)[ it can be found arbitrary large values for Conn(~'(G),~(G)). We give an example with val(G)=2 = I~(a)l. Let C, be a cycle with n edges. Then the graph G=C, × Y_U{v × ~; vE V(C,)} verifies Conn(~-(G), ~(G)) = n. Now we turn our interest to 2-complexes. For them we have the following. Proposition A.6. Any infinite admissible 2-complex P with I~-(P)I ~>2 verifies: (a) Conn(g(P), ~2(P)) = Conn(g(P), #(P)) = min{Conn(e(P), ~-(P)), Conn(~z(P), :2(P))}. (b) max{Conn(8(P),~(P)),Conn(J~2(P), .-~2(P))}~< Conn(..~(P),.~2(P)) ~< min{Conn (if(P), ~(P)), w2(P)}. Here w2(P)=min{w(A),AE~2(P)} denotes the width of P and w(A) is the width of the 2-end A; i.e. the maximal number of independent 2-rays defining the 2-end A. On the other hand, it is clear that Conn(g(P),cxz)~<val(P). Furthermore we can prove Proposition A.7. For an infinite admissible 2-complex P with [~2(P)[ I>2 the following equalities hold: (a) min {Conn (8(P), cx~), Conn (~2(P), ~2(P))} = Corm (g(P), J2(P)) =Conn (g(P), #(P)). (b) min{Conn(~(P), c~), Corm(if(P), ~-2(P))} = Conn(8(P), if(P)). R. Ayala et al. / Discrete Mathematics 194 (1999) 13~7 35 Corollary A.8. The number Conn(~(P), g(P)) = Conn(~(P), ~2(P)) is the smallest connectivity order of P. In addition, if P b an infinite admissible 2-complex with only one 2-end then all the connectivity orders defined for P are the same. The proof of Propositions A.6 and A.7 need the following lemmas involving the family of cut-sets 5~(A, B). Lemma A.9. For P as above we have: (a) o~(#(p), y(p)) C_ 6a(ov(P), ,,~2(P)) = ~(o#(P), ~f(P)). (b) ~5,(~(°~-(P), Y(P)) c_ 6#(~(p), ~2(P))= ~(~2(P), ~2(P)). (c) ~(e(P), g(P)) = 5~(o~(P), if(P)) U 5~(ff2(P), ~-2(P)). Proof. (a) Clearly, if J separates the edge e from the end e then J separates e from any 2-end A E h-l(e) (see Proposition 2.4). In order to show the equality in (a) we just mimic the proof of Lemma A.1 by using the identification ff2(P)= ~(G(P)) in Proposition 2.4. (b) If J separates e and d in Y(P) then J also separates e (d respectively) of any 2-end A~E h-I(e ') (A E h-l(e) respectively). (c) The inclusion 6e(~2(P),~2(P))c 5P(eg(p), g(p)) follows from Proposition 2.4 and the same proof as in (A.l(a)), and so 5~(~2(P),~2(P))USc(g(P)),~(P))C_ 5¢(~(P),ov(P)) by (a). Assume now J E 5P(g(P), g(P)). If J ~ 5P(8(P),~(P)) the complement P- J has at least two 2-path connected components and all of them are infinite, otherwise J would be a cut-set in 5¢(g(P)),,,~(P)). Hence J E 5~(Y2(P),~2(P)). If J ~ 5P(J2(P), ~2(P)) the complement P - J has at least two 2-path components but only one of them can be infinite. Therefore J ~ 5e(g(P), ~(P)). [] Lemma A.IO. For P as above we have (a) fD(~(p), oo) U o~(~2(P), o~2(P)) = &a(g~(p), ~2(P)). (b) 5 ° (g~(P), ~o) U 5 P (~(P), o~2(P)) = 5 ~ ($(P), o~ (p)) = 5P (~(p), oo) u ~ (~(P), o~(p)). Proofl (a) This follows from the identification ~-2(P)= ~(G(P)) in Proposition 2.4 and by the same proof as in Lemma A. l(b). (b) Given a cut-set J for e E o~(P) and oe, it is clear that J separates e from any Freudenthal end e E oj(p). Similarly, given a cut-set J for e E o~(p) and A E o~2(P) we have that J separates e from any interior vertex in the connected component C j c_ P-J which defines A. Moreover, if J E S#(~(P), o~(p)) - cf(g(p), o~2(p)), j separates an edge e E ~(P) of a Freudenthal end e E o~(p), and by Lemma 2.1 e must lie in a finite connected component of P -J. Therefore J E ~9°(¢(P), c~), and the first equality is proved. The second equality is checked in a similar way. [] 36 R. Ayala et al./Discrete Mathematics 194 (1999) 13-37 Proof of Proposition A.6. (a) By using Lemma A.9(a) and (c) we can easily check Conn(8(P), ~2(P)) = Conn(6~(P), g(P)) < min{Conn(o~(g), ~(P)), Conn(~2(P), J~2(P))}. Furthermore, if Conn(8(P), 8(P)) = n < Conn(¢(P), ~,~(P)), by Theorem 2.14 there exists a cut-set J E ~(6~(P), 8(P)) with l J[ = n. In particular, J ~ H'(8(P), ~(P)), and hence J E ~9°(~2(P),~,~2(P)) by Lemma A.9(c). So Conn(~2(P),~2(B)) = n. In case n<Conn(~2(P),,~2(P)), we can use Lemma A.9(c) again to show Conn(6~(P), ~-(P)) ----- n. (b) By using Lemmas A.9(b) and A.10(b) one gets Conn(~2(P),~2(P))~<Conn (~(P), ~-2(P)) ~< Conn(o~(P), ~(P)) and Corm(e(P), #-(P))-<< Conn(~(P), ~2(P)). Finally, one easily checks Conn(~-(P),~2(P))<~w2(P). [] Proof of Proposition A.7. (a) Here we follow the same arguments as in the proof of A.2(c) by using Lemmas A.9(a), (c) and A.10(a). (b) It follows the same pattern as the proof of A.2(c) by using now A.10(b). [] Example A.11. The following admissible 2-complex P shows that the inequalities in Proposition A.6 can be strict. Let X be as in Example 2.3 and let X' be the symmetric copy of X with respect to the axis OY. We consider the space Y -- [-2, -1] × [-4,4]U X UX' U [-1,2] × ([2,4] U [-4, -3]). Then P is the admissible 2-complex obtained as a subdivision of the following cellular decomposition of X without new vertices: y = We have Conn(8(P), ~-(P)) = Conn(~2(P), ~2(P)) = 1, Conn(Y(P), ~-2(P)) = 2 and Conn(~(P), ~-(P)) = w2(P) = 3. Acknowledgements This work was partially supported by the project DGICYT PB96-1374. References [1] D. Barnette, Decompositions of homology manifolds and their graphs, Israel J. Math. 41 (1982) 203-212• [2] G. Dirac, Connectedness and structure in graphs, Rend. Circulo Mat. Palermo 9 (1960) 114-124. R. Ayala et al./ Discrete Mathematics 194 (1999) 13-37 37 [3] G. Dirac, Extensions of Menger's theorem, J. London Math. Soc. 38 (1963) 148-163. [4] H. Freudenthal, U-ber die topologischer Raiime und Grupper, Math. Z. 33 (1931) 692-713. [5] R. Halin,/,]-ber Trennende Eckenmenger in Graphen und der Mengerschen Satz, Math. Ann. 157 (1964) 34-41. [6] R. Halin, Zur Theorie der n-fach Zusammenhangenden Graphe, Abh. Math. Sem. Univ. Hamburg 33 (1969) 133-14. [7] R. Halin, Die Maximalzahl fremder zweiseitig nnendlicher Wege in Graphen, Math. Nach. 44 (1970) 119-127. [8] R. Halin, A Note on Menger's Theorem for Infinite Locally Finite Graphs, Abh. Math. Sem. Univ. Hamburg 40 (1974) 111-114. [9] D. K6nig, Theory of Finite and Infinite Graphs, Birkhaiiser, Basal, 1990. [10] D.R. Linck, Characterization of n-connected and n-line connected graphs, J. Combin Theory Ser. B 14 (1973) 122-124. [11] K. Menger, Zur allgemeinen Kurventheorie, Fundam, Math. 10 (1927) 96-115. [12] N. Polat, Topological aspects of infinite graphs, in: G. Hahn, G. Sabidussi, R.E. Woodrow (Eds.), Cycles and Rays, Mathematical and Physical Sciences, vol. 301, Kluwer, Dordrecht, 1990. [13] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168. [14] EY. Woon, n-Conneetedness in pure 2-complexes, Israel J. Math. 52 (1985) 177-192.