On the connectivity of infinite graphs and 2-complexes

DISCRETE MATHEMATICS ELSEVIER Disc e e Ma hema ics 194 (1999) 13-37 On he connec i i y o in ini e g aphs and 2-complexes R. Ayala a'*, M.J. Ch i ez b, A, M i quez c A. Quin e o a a Depa amen o de Geome la y Topologia, Facul ad de Ma em& icas, Uni e sidad de Se illa. Apa ado 1160, 41080 - Se illa, Spain b Depa amen o de Ma em6 icas Aplicadas L Escuela de A qui ec u a Tkcnica, Uni e sidad de Se illa. A da, Reina Me cedes s/n, 41012 - Se illa, Spain c Depa a nen o de Ma em& icas Aplicadas I, Facul ad de ln o m~ ica, Uni e sidad de Se illa, c/Ta ia s/n, 41012 - Se illa, Spain Recei ed 14 Ma ch 1997; e ised 5 Sep embe 1997; accep ed 8 Decembe 1997 Abs ac This pape con ains a s udy o he connec i i y o in ini e g aphs and 2-complexes. Va ious connec i i y ypes a e de ined and ela ionships among hem a e gi en. In addi ion new Menge - Whi ney ype heo ems a e s a ed o bo h g aphs and 2-complexes. @ 1999 Else ie Science B.V. All igh s ese ed AMS classi ica ion: p ima y 05C40; seconda y 57M20 Keywo ds. Connec i i y; End; (Bi) ay; (Locally ini e) g aph; 2-(bi) ay; (Locally ini e) 2-complex O. In oduc ion Many esul s conce ning he no ion o connec i i y can be ound in g aph heo y. The classical esul on connec i i y is he well-known Menge -Whi ney Theo em (MWT o sho ) which shows ha o any wo e ices o a g aph, he maximum numbe o pai wise disjoin pa hs joining hem is equal o he minimum numbe o e ices needed o sepa a e hem [11,13,9]. A wo-dimensional analogue o he MWT o ini e 2- complexes is gi en by Woon in [14], whe e a 2-pa h is de ined as an o de ed sequence, o pai wise adjacen 2-simplices. In addi ion, Woon posed he ques ion o ex ending his esul s o in ini e 2-complexes. * Co esponding au ho . E-mail: quin e o@cica,es. 0012-365X/99/$-see on ma e (~) 1999 Else ie Science B.V. All igh s ese ed PH S0012-365X(98)00033-8 14 R. Ayala e al./ Disc e e Ma hema ics 194 (1999) 13-37 The aim o his pape is o answe Woon's ques ion. We in oduce a ious ypes o connec i i y conce ning he ideal poin s a in ini y o an in ini e 2-complex K and hen we p o e se e al MWT ype heo ems o such connec i i y ypes. These esul s a e con ained in Sec ions 2 and 3. Inciden ally, we p o ide a mo e gene al and sho e p oo o Woon's main heo em in Sec ion 2. In pu suing ou aim we ha e ound and used se e al heo ems ela ed o al eady known ex ensions o he MWT conce ning he ideal poin s a in ini y o an in ini e g aph [12,5,8]. These esul s seem o be new in he li e a u e and we ha e included hem in Sec ion 1. Finally, in Appendix A, we gi e se e al ela ionships among he di e en connec- i i y ypes in oduced in his pape o bo h g aphs and 2-complexes. We nex gi e he basic no a ion we shall use along his pape . We ecall ha a simplicial complex, K, is a se o simplices such ha : (a) I a E K and ~ is a ace o ~ (~ <a, o sho ) hen T E K. (b) I a, a ~ E K hen a A & is emp y o a common ace o a and &. The complex K is locally ini e i any a E K is he ace o only ini ely many sim- plices o K. Fo a E K he s a o a in K is he subcomplex s (a; K) = (#; ~ E K wi h # <T and a < z}. The link o a in K is he subcomplex lk(a;K)= {# E s (a;K); a A ~=O}. A subcomplex L o K is a complex whose simplices a e simplices o K. Gi en a subcomplex L c_ K, he no a ion K L will s and o he subcomplex o K gene a ed by K-L; ha is, K L= { E K; <p and p ~L}. The i-skele on o K is he subcomplex ski K C K consis ing o all simplices a E K wi h dim a ~< i. We say ha K is pu ely n-dimensional when any simplex a E K is he ace o some n-simplex o K. Fo he sake o simplici y, we shall say ha K is an n-complex when K is a pu ely n-dimensional locally ini e connec ed complex. Le a be an (n - l)-simplex o an n-complex K. The alence o a, al(a), is he numbe o n-simplices in s (a; K). The alence o K is he numbe al(K) : min{ al(a); dim a = n - 1 }. An (n- 1)-simplex c E K is said o be a bounda y simplex when al(c )= 1. O he - wise we say ha ~ is an in e io simplex. The bounda y o K, OK, is he smalles subcomplex o K con aining he bounda y simplices. The bounda y OK is said o be ull when any simplex in K mee s OK in a (possibly emp y) ace. Gi en an inc easing sequence o ini e n-subcomplexes KiCin Ki+~ (i~>1) wi h OG K = Ui~l Ki, a F euden hal end o K is a dec easing sequence (Ci)i~>l o in ini e con- nec ed componen s Ci C_K- Ki (i>>, 1). We ecall ha he e a e only ini ely many in ini e connec ed componen s in K- Ki o each i~>l. Le ~(K) be he se o F euden hal ends o K. I easy o check ha ~(K)=o~(sk 1K). Mo eo e , i can be p o ed ha ~(K) can be opologized in such a way ha ~(K) is homeomo - phic o a closed subse o he Can o se . See [4] o mo e de ails on he space ~-(K). R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13 37 15 1. Some Menge -Whi ney ype heo ems o in ini e g aphs Fo a g aph we mean a connec ed 1-complex G. In pa icula G will always be locally ini e. Le V(G) deno e he se o e ices o G. A pa h ~ : ao- an be ween wo e ices a0, an E G is a ini e sequence o e ices {a0 ..... an} such ha ai ~ aj (i ~ j) and he segmen (ai, ai+l) is an edge o G (O<~i<<.n - 1). A pa h ~ be ween he se s A,BC_ V(G) is a pa h c~:ao-an wi h ~NA={a0} and ~NB---- {an}. A (one-way) ay R : a0 - ec s a ing a a0 E G is a sequence o e ices {a0 .... } such ha ai :~ a/ (i C j) and (ai, ai+l) is an edge o G. A ay be ween 17 c_ V(G) and in ini y (~, o sho ) is a ay R s a ing a some eel7, wi h II•R={e}. I is clea ha a ay de ines a unique F euden hal end. Mo eo e i is no ha d o show ha he F euden hal ends o G can be desc ibed as equi alence classes o ays, whe e wo ays R and R I a e ela ed i he e exis s a ay R" whose in e sec ions wi h R and R' a e in ini e (see [12] o de ails). A ay R : a0-e be ween a0 E V(G) and e E Y(G) is a ay s a ing a a0 which de ines he end e. Simila ly we can de ine a ay be ween he se s 17 C V(G) and F C_ ~(G). Finally, a bi ay (o wo-way ay) wi h sou ce e and a ge e/R : e - e/ is a sequence o e ices indexed by he se o in ege numbe s 7/{... a-2,a-l,a0,al, a2...} such ha aiCaj (iCj), he segmen (ai, ai+l) is an edge o K, and R de ines he ends e.,e' E Y(G). Simila ly we can de ine a bi ay be ween F,F'C_ ~(G). Two pa hs ( ays, espec i ely) ~, l:a-b (~,/3 :a-oo, esp.) a e said o be indepen- den when 7 N/3 = {a, b} (~ n/3 = {a}, esp.). Two bi ays a e independen when hey a e disjoin . The dual no ion o independen pa hs is he no ion o cu -se . When we in oduce he ends and he in ini y poin oo o a g aph, di e en no ions o cu -se can be con- side ed. Namely, gi en a ( ini e) se o e ices J C V(G) we say ha J is a cu -se o a, bE V(G) i a and b lie in di e en connec ed componen s o G- J. No ice ha J exis s since G is locally ini e. Mo eo e , he se J is a cu -se o a E V(G) and oc i a lies in a ini e connec ed componen o G -J. Gi en a E V(G) and E ~(G) we say ha J is a cu -se o a and e when a does no lie in he connec ed componen ~ C_ G - J which de ines e. Finally, J is a cu -se o ~,e E ~-(G) when Fo he sake o simplici y by a ajec o y we shall mean a pa h, a ay, o a bi ay acco dingly o he con ex . Va ious Menge -Whi ney ype heo ems ela ing he di e en cu -se s and he co e- sponding se s o independen ajec o ies can be ound in he li e a u e. In o de o deal wi h hem in a simple way we conside he se o symbols {V(G),oo, Y(G)} and we choose he pai s (V(G), V(G)), (V(G),oe), (V(G),Y(G)), and (~-(G),~(G)). Any o hese pai s is called a connec i i y pai . Gi en a connec i i y pai (A,B) and a E A and b E B wi h a ~ b, he connec i i y o - de o (a, b) is he maximum numbe Conn(a, b) o independen ajec o ies om a o b. The connec i i y o de o he pai A0 CA, B0 C B is he numbe Conn(Ao, B0)= min {Conn(a, b); a E Ao, b E B0, a ¢ b}. The connec i i y o de o ype (A, B) o G is he 16 1~ Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 numbe Conn(A,B). We say ha G is n-connec ed o ype (A,B) i Conn(A,B)>~n. No ice ha o one-ended g aphs only he connec i i y o de s o ype (V(G), V(G) and (V(G), oo)) = (V(G), ~(G)) a e de ined. Fo he connec i i y pai (A,B), le 6P(A,B) deno e he amily o all cu -se s o ype (A,B), i.e. 5P(A,B)= U{Se(a,b); aEA, bEB, a¢b} whe e 5e(a,b) is he am- ily o all he cu -se s o a, b in G. Mo eo e , he cu -o de o (a, b) is he numbe Sep(a,b) =min{[J[; J E 6e(a,b)}. He e IJI deno es he ca dinal numbe o J. No ice ha hese numbe s a e ini e since G is locally ini e. Then he ollowing gene al o m o he Menge -Whi ney heo em holds. Indeed o he pai s (V(G), V(G)), (V(G), oo), (V(G), ~-(G)), and (~(G), ~(G)) he co esponding p oo s can be ound in [9, 7, 8,12] espec i ely. Theo em 1.1. Fo any connec i i y pai (A,B) and a E A, b E B wi h a ~ b, Sep(a, b)= Conn(a,b). In pa icula , he connec i i y o de Conn(A0,B0) coincides wi h he cu - o de Sep(Ao, Bo) -- min{ [J I; J E 5P(a, b); a E Ao, b E Bo; a 5~ b} o any pai Ao C A and Bo C_ B. In o de o keep his sec ion wi hin a sensible leng h we shall gi e he ela ion- ships among he di e en connec i i y ypes in Appendix A. We now p oceed o gi e some consequences and a ia ions o he Menge -Whi ney heo em s a ed abo e o he a ious connec i i y ypes de ined he e. They a e he analogues o al eady known esul s in ol ing he connec i i y ype (V(G), V(G)) and he classical Menge -Whi ney heo em. Fo he connec i i y ype (V(G),oo) we can p o e he ollowing heo ems Theo em 1.2 (Di ac [3, Theo em B]). Le G be an in ini e g aph, hen he ollowing s a emen s a e equi alen : (a) G is n-connec ed o ype (V(G),oo). (b) Le A = { l,..., Vp} be a ini e se o e ices o G. Gi en any amily {al ..... ap} o posi i e in ege s wi h ~P=~ ai = n he e exis n independen ays om A o oo such ha ai o hem s a om i, o all i. (c) Gi en any se o e ices A C V(G) wi h [A[ = n he e exis s a amily o n disjoin ays om A o c~. P oo . (a) =~ (b): I is a pa icula case o P oposi ion 1.7 below; see Rema k 1.8. (b) =~ (c): I is ob ious. (c) ~ (a): Clea ly, condi ion (c) implies ha al(G)~>n. O he wise, i E V(G) is a e ex wi h al( )~<n- 1, we can o m a se A C_ V(G) con aining { } Ulk( ; G) wi h [A[ =n and (c) does no hold o A. As al(G)~>n, hen Ilk( ; G)[ ~>n o all E V(G), and by condi ion (c) we can ind n disjoin ays s a ing a n e ices in lk( ; G), and hese ays yield n independen ays s a ing a . This inishes he p oo . [] R. Ayala e aL/Disc e e Ma hema ics 194 (1999) 13-37 17 Theo em 1.3 (Linck [10]). Le G be an in ini e g aph. Then he ollowing s a emen s a e equi alen : (a) G is n-connec ed o ype (V(G),cxD). (b) Gi en a se AC_ V(G) wi h IAI--n- 1, o any e ex yEA he e exis s a bi a RCG wi h RNA={ }. (c) Gi en a se B c V(G) wi h IBI = n, o any e ex E B he e exis s a ay R c_ G wi h Rn~= { }. P oo . (a)~(b): Gi en AC_ V(G) wi h [Al=n- 1, we ake yEA. Since G is n- connec ed o ype (V(G),oo) we can ind n independen ays s a ing a . Hence a leas wo ays do no con ain e ices in A o he han . These wo ays de ine a bi ay R wi h R NA = { }. (b) ~ (c): The e exis s a bi ay R which con ains and a mos a e ex ~ E B. Then i is clea ha we can ind a ay R~C_ R con aining wi h R~N B = 0. (c) ~ (a): Le J C V(G) be any se o e ices wi h IJI ~<n- 1, Gi en any e ex E G-J, by using (c) we can ind a ay R C G such ha E R and R nJ : 1~. The e o e, he connec ed componen o in G-J is in ini e, and J ~A~(V(G),oc). [] Theo em 1.4 (Di ac [2] and Halin [6]). Le G be an in ini e s-connec ed 9 aph. Then he ollowing s a emen s a e equi alen : (a) G is n-connec ed o ype (V(G),cx~). (b) Fo A = { l,...,Vn--1} ~ V(G) and 1 ~<m~<min{s + 1,n - 1} he e exis s a bi ay R C G wi h R NA = { l ..... Vm}. (c) Fo B= { l ..... n} C_ V(G) and 1 ~<m~<min{s ÷ 1,n} he e exis s a ay R C_ G wi h R NA = {Vl ..... m}. P oo . (a) ~ (b) The case m --- 1 is Theo em 1.3. Assume we ha e al eady p o ed (b) o m<<,k - 1 <<,s. Le R be a bi ay wi h RNA = { l ..... Vk-1}. Gi en k EA, by using Theo em 1.2b we can ind k+ 1 independen ays L~ ..... L~+j om k o oc which do no mee { k+l ..... ,-1}. When RNLi 7&0, le ai E V(Li) deno e he i s e ex in R (l<~i~<k+ 1). The e ices l ..... k-1 de ine a decomposi ion o R in o k- 2 pa hs R1 ..... Rk-2 and wo ays R_~, R~. Assume ha wo e ices as, a lie in he same pa h ( ay) Rj (l<~j<~k- 2, j= + cx~). Then a bi ay can be ound in RUL~.ULI con aining { l ..... k}. He e L~ C_Li deno es he pa h om k o ai. The e o e, we can now assume ha a leas one ay Li does no mee R. In case ha only Ll misses R, we can assume ha each ai (2<~i<~k + 1) de ines a unique pa h o ay Rj(i) (1 <~j(i)<~k -2, j(i)= 4-~). Hence, a sui able bi ay can be ound in R U L1 U LI 0 whe e j(io)= 4-~. A his poin i will su ice o assume ha a leas wo ays Li miss R. As G is s-connec ed we can also ind a se o s independen pa hs 7j: k - j (j¢k). Le biE~'i (l<~i<~k- 1) deno e he i s e ex in 7inR. I no b~ lies in R_~ URn, he e mus exis a pa h R/ con aining wo e ices bp, bq and hence a bi ay 18 R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 R'CRUVpUTq can be easily ound wi h { l ..... k}CR'. He e 7pC),p deno es he pa h om ~ o bp. Assume now bl ERos. As he e a e wo ays Lp,Lq which a e disjoin wi h R, we can assume wi hou loss o gene ali y ha Lp AVl = { k}, and i is clea ha a bi ay can be ound in RULp UTl con aining { l ..... k}. The p oo o (a)=:> (c) is simila and we omi i . Mo eo e , (b)~ (a) as well as (c) ~ (a) ollow om Theo em 1.3. [] Example 1.5. Any in ini e ee G wi h all e ices o alence n~>4 shows ha Theo em 1.4 does no hold wi hou he hypo hesis on he connec i i y o G. Indeed, G is 1-connec ed o ype (V(G),V(G)) bu n-connec ed o ype (V(G),oo). Mo e- o e , G does no sa is y ei he (b) o (c) in Theo em 1.4 o m : 2. We nex gi e simila heo ems o he connec i i y ype (V(G),~(G)). We s a wi h he ollowing cha ac e iza ion Theo em 1.6 (Di ac [3, Theo em B]). Le G be an in ini e 9 aph, hen he ollow& 9 s a emen s a e equi alen : (a) G is n-connec ed o ype (V(G),~(G)). (b) Gi en wo se s A = { l ..... Vp} C_ V(G) and B = {el ..... ~q} C_ ~(G) and wo se s o posi i e in ege s {al ..... ap} and {b~ ..... bq} wi h ~-~ =lak= ~-~qh=~bh=n, he e exis n independen ays om A o B such ha ak o hem s a a k and bh o hem de ine eh o all k, h. Theo em 1.6 is an immedia e consequence o he ollowing mo e gene al p oposi ion which will be used also o 2-complexes in Sec ion 3 below. P oposi ion 1.7. Le G be an in ini e 9 aph A = {Vl ..... Vp} C V(G), and M = {BI ..... Bq} a amily o pai wise disjoin closed se s o F euden hal ends o G. Assume ha o each pai (k,h) he e exis n ays unning om k o Bh. Then 9i en wo se s o posi i e in ege s {al ..... ap} and {bl .... , bq} wi h ~-~Pl ak = ~-~q=l bh = n, he e exis n independen ays om A o [-Jq=l Bh such ha ak o hem s a a k and bh o hem end a B h o all k, h. P oo . Fi s we conside a amily ~(k,h) o n pai wise disjoin ays om k o Bh and le ~(k,h)C_Bh deno e he se o ends de ined by he ays in ~(k,h). Then we choose a connec ed ini e subg aph K C G such ha s @k; G)CK o all k EA and mo eo e he connec ed componen s V~ C_ G-K de e mined by he ends e c U {~(k, h); 1 ~<k ~< p, 1 ~<h ~<q} a e pai wise disjoin in such a way ha he ays in :~ = [_J {~(k, h); 1 <~k<<.p, 1 <~h<~q} which mee V~ a e exac ly hose de e mining e. Fu he mo e, o each R E ~(k,h) wi h end e E ~(k,h) le TR C R N V~ be a sub ay o R. Gi en eE~(k,h) we o m he amily ~Y'-~. consis ing o all ays TR whe e RE~, and o~(R)= e and we choose a sub amily J/g~ _C ~ such ha [J/~[ = max{[~ g~[; ~,~ C_ ~ and he ays in ~ a e pai wise disjoin }. R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13~7 19 Nex o each R E ~ wi h ~(R) = e and TR ~ ~/,: we choose n pai wise disjoin pa hs in V~ joining R o all ays in J/0. We call hem he ne o R and we deno e i by ~.4~. No ice ha some pa hs in JV8 may be degene a e one-poin pa hs. We ake a new ini e subg aph G~c_ G con aining K, all pa hs in he ne ~.~ o each R, and mo eo e a subpa h in each R (in J//~ o no ) passing h ough all poin s in R ob ained as in e sec ion o R wi h he pa hs in he ne s. Fu he mo e, we equi e ha each T E J '~; mee s he on ie F (G') = G ~ N (G G') in jus one e ex. He e G G' is he subg aph gene a ed by G - G', see In oduc ion. Then o each k and h we conside he se s o e ices Fk=lk( k;G)- A and Oh=F (G')N(U{T; TEJCI~ and eEB~}). No ice ha Fk ¢i~ o all k since p<~n. We now cons uc a new g aph Go as ollows. We ake pai wise disjoin se s {Dk}l<~k<~p and {Eh}l<~h<~q wi h IDkl=a~ and LEhl=bh. Then we o m he com- ple e bipa i e g aphs Lk =K(Dk,Fk) and L~ =K(Eh, Oh). Finally, we conside wo u he e ices c and c ~ and he comple e bipa i e g aphs C=K(c, UP l Dk) and C'=K(c',Uq j Eh) and we se Go= (G'~C_LJs ( k;G))U (kO1Lk)U (j~,L~)UCUC'. We claim ha Conn(c,c')>~n in Go. Indeed, le JCGo be a se o e ices wi h [JI ~<n- 1. Then one inds x0 EDko -J and Y0 EEho -J o some k0 and h0. Mo eo e , he e exis s a leas one ay R E ~(k0, h0) which does no mee J. Howe e , R may con ain some o he e ices j E A-{ k0 }. We p oceed o show ha i is always possible o choose R in such a way ha o any j E A A R we ha e Di -J 7 ~ ). O he wise, all ays in ~(ko, ho) which a oid JNG=J71G' con ain some iEA wi h D/C_J. Le I = {k;D~ c J}. Then one ge s necessa ily n = I~(k0,h0)[ <~ [J N G U { k; k EI}[. Mo eo e , since Dk C__ J o all k E I one ge s also IJ N G] ~<n - 1 - ~kc~ ak. This leads o he con adic ion n ~< [J A G[ + 1I[ ~<n - 1. The e o e, we ha e p o ed he exis ence o a non-emp y subse 5a(k0, h0) C ~(k0, h0 ) consis ing o ays R which do no mee J and o all j ERNA we ha e Di-J 7~ ~. We conside he amily o ends C~(ko, ho) = {e ~_ Y(k0,h0); e = ,~-(R) wi h R E L (k0,h0)}. We call an end in W(k0, h0) a clean end. We nex show ha he e exis s a clean end e0 such ha some To E J/~:,, does no mee J. O he wise, i m,: = [.//g~.[ and I = {k;D~ C J} we ha e we ha e m~<~(n-1)- ~ak- , ~C6(ko,ho ) k~l whe e = [J - U~.E~(k~,h0) ~[. In addi ion, i w,: is he numbe o ays in :~(ko, ho) which de ines he end e, he maximali y o ~¢/~: and he abo e inequali y yield w,: <~ ~-~ ( ko, ho ) n~ <. ( n -1) - ~ w~:, ~:~'(ko, ho ) ~c~ ~/G~-(ko, ho) ~ (k~l,ho) since ~e,E,N(ko,ho)_~g;(ko,ho) W e, <<. + III. Hence n = ~.~(~o,ho) w,: ~<n -- 1 which is a con adic ion. 20 R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 The e o e, we ha e p o ed ha he e exis s eoECg(ko, ho) and ToEJ//~o wi h To A J = 0. Hence, he e exis s a ay Ro E La(k0, h0) wi h i (R0)= e0. In addi ion, he cons uc ion o he g aph G p allows us o choose a pa h 70 c G ~ om R0 o To such ha he union U=7oURoUTo misses he se J. Mo eo e , A q(ToMT0)=0 and i (A - {Vko}) NRo ¢ ~ we can eplace Vko by he las e ex in R0 NA since Dj - J ¢ 0 o all j E Ro A A. Fo his we use ha R0 E 5¢(k0, ho). So, we can assume, wi hou loss o gene ali y, ha UAA={ ko} and hen we easily connec c o c' in Go by a pa h passing h ough x0, U, and yo. We ha e checked ha Conn(c,c~)>>.n in Go and he Menge -Whi ney heo em o he connec i i y pai V(G), V(G) in (1.1) p o ides n independen pa hs 71,72 ..... 7n in Go om c o c ~. In pa icula , ),j q G ~ (1 <<.j<~n) a e pai wise disjoin pa hs wi h 7j M G' unning om some I'k(j) o some Oh(j). Mo eo e , o each k and h only ak and bh, espec i ely, o he pa hs 7j M G e i y k(j)=k and h(j)=h, espec i ely. Now i is clea ha {7j M G~}I <~j<~n can be ex ended o a amily o n independen ays wi h he equi ed p ope ies. This inishes he p oo . [] Rema k 1.8. Since a ay s a ing a is jus a ay unning om o i (G), one ge s (a) =~ (b) in Theo em 1.2 as a pa icula case o P oposi ion 1.7 by se ing q = 1 and B~ = i (G). O he esul s conce ning he connec i i y pai (V(G), ~(G)) a e he ollowing. Theo em 1.9 (Linck [10]). Le G be an in ini e g aph. Then he ollowing s a emen s a e equi alen : (a) G is n-connec ed o ype (V(G),~(G)). (b) Gi en AC_ V(G) wi h [A[=n - 1, o any e ex yEA and any end eEl(G) he e exis s a bi ay R C G wi h bo h ends ~ and R MA----{ }. (c) Gi en a se BC V(G) wi h IBI =n, o any e ex cB and any end ~E~-(G) he e exis s a ay RC G whose end is ~ and such ha RMB= { }. The p oo o Theo em 1.9 ollows he same pa e n as he p oo o Theo em 1.3 and we omi i . Mo eo e , since Conn(V(G),~(G))= Conn(V(G), V(G)) (see P oposi ion A.2) we ge he ollowing analogue o he (1.4) abo e Theo em 1.10 (Di ac [2] and Halin [6]). Le G be an in ini e g aph. Then he ol- lowing s a emen s a e equi alen : (a) G is n-connec ed o ype (V(G),~(G)). (b) Fo A={Vl ..... n_l} C_ V(G), eEJ~(G), and l <~m<~n- 1 he e exis s a bi ay R whose only end is ~ and such ha R NA ~- { l ... Vm}. (c) Fo B={ l ..... n} C_ V(G), eEl(G), and l <<.m<<.n he e exis s a ay R whose only end is ~ and such ha R NA = { l ..... Vm}. The p oo is simila o he p oo o Theo em 1.4. We lea e i o he eade . R. Ayala e aL /Disc e e Ma hema ics 194 (1999) 13 37 21 Theo em 1.11. Le G be an in ini e g aph. Then he ollowing s a emen s a e equi - alen (n>~2 and I~(G)I >_-2): (a) G is n-connec ed o ype (V(G),~.~(G)). (b) Fo A = { ..... ,_ } C V(G), e, d E ~(G), and 1 ~m<~n- 1 he e exis s a bi ay R whose ends a e e and d and such ha RNA = {Vl ..... Vm}. P oo . (a)~(b): By using (a) we can ind wo ays R1,R2 om l o e, such ha RinA={ l} (i= 1,2). Simila ly he e a e wo ays R~ (j= 1,2) om l o d wi h he same p ope y. As e # d each in e sec ion R~ n Rj is ini e. I is now easy o con- s uc a bi ay R C_RI UR2 UR'~ UR~ wi h J~(R)= {~,d} and RNA = { ~}. Hence, we ha e shown (b) o m = 1. A his poin we can ollow he pa e n o he p oo o Theo em 1.4 o p o e (b). The con e se (b)~ (a) ollows om Theo em 1.9, [] Fo he connec i i y pai (~-(G),~(G)) we can p o e an analogue o Theo em 1.6. Ac ually we shall use P oposi ion 1.7 o p o e a mo e gene al esul . Namely P oposi ion 1.12. Le G be an in ini e g aph and ~¢ = {Al ..... Ap} and ~ = {B ..... Bq} wo amilies o closed se s o F euden hal ends o G such ha he elemen s o ~4UM a e pai wise disjoin . Assume ha o each pai (k,h) he e exis n bi- ays unning om Ak o Bh. Then gi en wo se s o posi i e in ege s {al ..... ap} and {bl ..... bq} wi h ~'~;-1 ak = ~-~q=l bh =n, he e exis n independen bi ays om P A uq_l Bh such ha ak o hem s a a Ak and bh o hem end a B~ [b Uk=l k o all k, h. P oo . Fi s o each pai (k,h) we choose a amily ~(k,h) o n pai wise disjoin bi ays om Ak o Bh. Le ~.~(k,h)- C_Ak and ~(k,h) + C_Bh deno e he se s o le and igh ends, espec i ely, de ined by he bi ays in ~(k, h). Then we conside a connec ed ini e subg aph K C_ G such ha he connec ed componen s V~ c_ G - K de ined by he ends c~E Uk.~(Y(k,h)-U~(k,h) +) a e pai wise disjoin . Mo eo e , we also assume ha he ays which mee V~ a e exac ly hose bi ays de e mining a. Then i R E ~(k, h) de ines he le end /, le TR C R n V~ be a sub ay o R con ained in he componen Vq. Gi en he le end q E ~(k,h)- we o m he amily Y, consis ing o all ays TR wi h R E U{~(k, h); 1 ~<k ~< p, 1 ~< h ~< q} and such ha /is he le end o R. Then we choose a maximal sub amily J/n C_ 3-'~ as in he p oo o (1.7) as well as ne s o pa hs ,A~ om all R ~ J/~ o he ays in #/,l" We now ex end he in ini e subg aph K U {~;~ E Uk, h (k,h) +} o a new g aph G' by adding ini e subg aphs in each V, wi h /E Uk, h~(k,h)- in such a way ha G' con ains all pa hs in he ne JVR o each R as well as a sub ay in R pass- ing h ough all poin s ob ained as in e sec ion o R wi h he pa hs in J VR. Fu - he mo e, we equi e ha o e e y le end / each ay T E ~/~ mee s he on ie F (G~) = G N(G G ~) in jus one e ex. Then o each k we conside he se o e - ices Fk=F (G')N(U{T; T E J/ln and /CA~}). We now cons uc a new g aph Go as ollows. We ake pai wise disjoin se s {Dk}l<,k<~p wi h [Dk[ =ak. Then we o m 28 R. dyala e al./Disc e e Ma hema ics 194 (1999) 13-37 P oo . By using he same a gumen s as in he p oo o P oposi ion 2.12 we ind n independen bi ays om i,l(h(H)) o i,I(F). These bi ays de ine n independen 2-bi ays in P joining H o F. [] The p e ious p oposi ions om P oposi ions 2.11 o 2.13 can be summa ized in he ollowing gene al Menge -Whi ney Theo em o admissible 2-complexes: Theo em 2.14. Le P be an admissible 2-complex P. Fo any connec i i y pai (A,B), i a E A, b E B and a ~ b hen Sep(a, b) = Conn(a, b ). In pa icula , he connec i i y o - de o ype (A, B) coincides wi h he cu -o de Sep(A, B) = min{Sep(a, b); a E A, b E B; a ~ b). No ice ha hese numbe s a e ini e since P is locally ini e. We inish his sec ion wi h a heo em which allows us o conside cu -se s con aining only edges o any ype o connec i i y. This heo em was o iginally p o ed by Woon [14, Theo em 3] o ini e 2-complexes and connec i i y pai (g(P),g(P)). We gi e he e a mo e gene al and simple p oo . Theo em 2.15. Le P be an in ini e admissible 2-complex such ha al(e)>>.n o any in e io edoe e E g(P). Then P is n-connec ed o ype (A,B) i and only i he e exis s no cu -se J E 5a(A,B) N ~(P) wi h IJ[ <n. Theo em 2.15 is an immedia e consequence o he ollowing Lemma 2.16. I J is a minimal cu -se o ype (A,B) o P wi h IJl=k <n, hen he e exis s a cu -se J' E 6~(A,B) M ~(e(P)) wi h IJ'I -- k. P oo . We shall p o e he lemma induc i ely on he numbe m >~ 0 o iangles in J. The case m = 0 is i ial. Assume ha he esul holds o m, and le J = { , l, 2 ..... m} U {am+l ..... ak-1 } be a cu -se o ype (A,B) wi h iangles , l, 2 ..... ,n. Gi en c E C, o any C E {8(P), oo, ~(P), ~,~2(P)}, le Ac deno e he se consis ing o all edges in P which can be joined o c by ajec o ies which do no mee J. I J is a cu -se o a E A and b E B we ha e Aa M Ab-----0. Mo eo e , since J is minimal he e exis s a se {7~}~ 6 J o independen ajec o ies wi h 7~ A J = {~} o each ~ E J. Gi en 7 , le ea (eb espec i ely) deno e he edge o which appea s in Aa -17 (Ab A ~) espec i ely). Finally, le e be he hi d edge o . Assume A,B = 8(P). Case 1: AeAAa=O. I ea=a, as al(a)~>n he e exis p iangles sl ..... Sp in s (a;P)-J. Mo eo e , since p>k- m- 1 he e exis s an edge d<sj wi h a ~J. Thus a E Aa, and any 2-pa h om a o b mus mee J. Fu he mo e, he assump ion Ae nAa = 0 yields ha any 2-pa h ~ :a'-b wi h ¢ NJ = { } mus con ain a. The e o e J1 = {a, l ..... m}U {am+l ..... ak--l} is a cu -se o a and b wi h only m iangles. R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 29 I a#e,, he assump ion AenAa=O implies ha J1 ={ea, l ..... m}U{am+l ..... ak-l} is a cu -se o a and b. Case 2: AenAa#O. As AanAb=O, i ollows ha AeNAb=q), and we p oceed in he same way by eplacing a by b. Assume A = g(P), and B # 8(P). In Case 1, he p oo is he same as abo e. In Case 2, he se J2={eb, h ..... m}U{am+l .... ,ak-I} is a cu -se o a,b wi h m iangles. Finally, assume A,BE{~2(P),:~(P)}. In Case 1 he se J3={ea, ,..., m}U {am+l ..... ak-l} is a cu -se o a,b. In Case 2 he se ./2 abo e is a cu -se . We now apply he induc ion hypo hesis o inish he p oo . [] 3. Some Menge -Whi ney ype heo ems o 2-complexes This sec ion con ains he wo-dimensional analogues o he esul s s a ed a he end o Sec ion 1. We ecall ha he analogues o (g(P),8(P))-connec i i y a e gi en in [14, Sec ion 4] o ini e 2-complexes. Ac ually, he same p oo s wo k o in ini e 2-complexes. We shall s a wi h he ollowing heo ems conce ning he connec i i y ype (g(P), o~). Theo em 3.1. Le P be an admissible in ini e 2-complex wi h al(P)~>n, hen he ollowing s a emen s a e equi alen : (a) P is n-connec ed o ype (8(P), oo). (b) Gi en A = {el ..... ep} C_ g(p) and any amily {al ..... ap} o posi i e in eye s wi h ~~P- 1 ai =- n he e exis n independen 2- ays om A o oo such ha ai o hem s a om ei, o all i. (c) Gi en any se o edges A C 8(P) wi h IAI--n he e exis s a amily o n indepen- den 2- ays om A o oe. P oo . (a)~(b): Acco ding o P oposi ion 2.9 Conn(E,~)=n o he se E o e ices o G(P) associa ed o in e io edges. Mo eo e , he se A yields a se ,4={~l,...,~n}CE and P oposi ion 1.7 applied o G(P) (see Rema k 1.8) shows ha he e exis n ays in G(P) ai o hem s a ing a el. Clea ly hese ays de ined he equi ed 2- ays in P. (b) ~ (c): I is ob ious. (c)~(a): Le J be a cu -se o P. As al(P)~>n we can assume ha JC_g(p) by Theo em 2.15. I IJ[<<,n- 1 and eES(P)-J we can apply (c) o JU{e} o ge a 2- ay R om e o ~ wi h RNJ=0 which is a con adic ion. So IJl>>,n, and P is n-connec ed o ype (8(P), oo). [] Theo em 3.2. Le P be an admissible in ini e 2-complex wi h al(P)>~n. Then he ollowing s a emen s a e equi alen : 30 R. Ayala e al./ Disc e e Ma hema ics 194 (1999) 1307 (a) P is n-connec ed o ype (8(P), oo). (b) Gi en a se AC_g(P) wi h [Al=n - 1, any edge eEA is con ained in a 2-bi ay which a oids he o he n- 2 edges o A. (c) Gi en a se B C_ g(P) wi h [B] = n, any edge in B is con ained in a 2- ay which a oids he o he n - 1 edges o B. P oo . (a)~ (b): By using P oposi ion 2.9 we ge Conn(E, cx~)= n in he he bipa i e g aph G(P). He e E is he se o e ices o G(P) co esponding o in e io edges. Mo eo e , he se A de ines a se A _C E. The same p oo as in (a) ~ (b) o The- o em 1.3 yields a bi ay R in G(P) which con ains a e ex ~E-~ and a oids he es o e ices o _~. The bi ay R clea ly de ines a 2-bi ay in P wi h he equi ed p ope ies. (b) =~ (c): I is ob ious. (c) =~ (a): I is simila o he p oo o (c) =¢, (a) in Theo em 1.3. [] Theo em 3.3. Le P be an admissible in ini e 2-complex. Assume ha P is s-con- nec ed o ype (g(P),8(P)) and al(P)~>n. Then he ollowing s a emen s a e equi alen : (a) P is n-connec ed o ype (8(P), oo). (b) Fo A ---- {el .... ,en-1} C 8(P ) and 1 <<,m <~ min{s+ 1,n - 1} he e exis s a 2-bi ay R C P wi h RNA = {el ..... e a}. (c) Fo A = {el ..... en} C 8(P) and 1 <~m <<. min{s + 1, n} he e exis s a 2- ay R c p wi h RNA = {el,...,em}. P oo . (a)~ (b): We know by P oposi ion 2.9 ha Co m(E,c~)=n and Conn(E,E) = s o he se E o e ices o G(P) co esponding o in e io edges o P. Mo eo e , he se A de ines a se ,4= {~1 ..... es+l} C E and he induc i e p oo o (a)~ (b) in Theo em 1.4 can be ca ied ou he e o ob ain a bi ay R in G(P) wi h RNA= {el ..... ~m}- The bi ay R yields he equi ed 2-bi ay in P. The p oo o (a)~ (c) is simila and we omi i . Mo eo e (b)~ (a) as well as (c) :=> (a) ollow om Theo em 3.2. [] Fo he connec i i y ype Conn(g(P),~2(P)) we ha e he ollowing esul which ollows he pa e n o Theo em 3.2. We lea e he p oo o he eade . No ice ha ~2(P)) is iden i ied wi h ~(G(P)) by P oposi ion 2.4. Compa e wi h Theo em 1.9. Theo em 3.4. Le P be an admissible in ini e 2-complex wi h al(P)~>n. Then he ollowing s a emen s a e equi alen : (a) P is n-connec ed o ype (g(P), ~,~2(P)). (b) Gi en a se A C g(P) wi h [A[ = n - 1, o any edge e EA and any end 6 E ~2(P) he e is a 2-bi ay R wi h bo h 2-ends A and such ha RNA = {e}. (c) Gi en a se B C ~(P) wi h IBI = n, any e E B and any 2-end A he e is a 2- ay R whose 2-end is A and such ha B N R = {e}. R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 31 Since Conn(g(P), 2(P))= Conn(g(P), 8(P)), we also ge he ollowing heo em. Theo em 3.5. Le P be an admissible in ini e 2-complex wi h al(P)>~n. Then he ollowin9 s a emen s a e equi alen : (a) P is n-connec ed o ype Conn(g(P), ~2(P)). (b) Fo A = {el ..... e,-l } C_ g(p), A E .~-2(P), and 1 <~m<<.n - 1 he e exis s a 2-bi ay R whose only 2-end is A and such ha R NA = {el ..... em}. (c) Fo B = {el ..... e,} C_ g(P), A E ~2(P), and 1 <<.m<~n he e exis s a 2- ay R whose 2-end is A and such ha RNB = {el ..... e a}. P oo . We know by Theo em 2.9 ha Conn(E,~(G(P))= Conn(E,E)=n. Now we can a gue as in Theo em 3.3 o show ha (a) implies bo h (b) and (c). The con e ses ollow om Theo em 3.4. Ano he esul o he same connec i i y ype is he ollowing heo em (compa e Theo em 1.11) whose p oo is also omi ed. Theo em 3.6. Le P be an admissible in ini e 2-complex wi h al(P)>~n and 1~-2(P)I/>2. Then he ollowin9 s a emen s a e equi alen : (a) P is n-connec ed o ype Conn(8(P), ~-2(P)). (b) Fo A={el ..... e,_l}Cg(P), A,A' c o~2(P), and l <~m<~n - 1 he e exis s a 2-bi ay R wi h 2-ends A,A ~ and such ha RNA= {el ..... em}. Fo he connec i i y ype ( 2(P), 2(P)) we can p o e he wo-dimensional ana- logue o (1.6) by applying (1.6) o he bipa i e g aph G(P) o P. We lea e he de ails o he eade . We inish his sec ion by conside ing connec i i y ypes o a 2-complex P in ol ing F euden hal ends. In gene al he e is no bijec ion be ween he F euden hal end o P and he F euden hal ends o G(P). Howe e , he analogues o Theo ems 3.2 and 3.3 o he connec i i y pai Conn(g(P),~(P)) hold. We lea e o he eade he ask o s a e and p o e hem. Nex example shows ha he hypo hesis on he connec i i y ype (g(P), g(P)) is necessa y o he analogue o Theo em 3.3. Example 3.7. Le M be any admissible 2-complex which is 3-connec ed o ype (g(P), g(P)) and wi h only one 2-end (e.g. he 2-skele on o any one-ended open 3-mani old. See Co olla y 2.7, and [1]). Le A = (x0 ..... x ..... } be any sequence o non-adjacen e ices o M. We conside h ee disjoin copies A i = (x/} CM/ (1 ~<i~<3) o A and M espec i ely and we cons uc he 2-complex P0 by iden i ying o a poin y, i o each n. Gi en y0 c P0 we ake h ee edges adjacen o y0, he h ee poin s x n 7i = (yO, Vi)cmi C Po, one in each copy Mi o M. Le c ~P0 and we conside he complex K0 wi h h ee iangles (c, yo, i) (1~<i~<3). We ake P=KoUPo. Then P has only one F euden hal end bu h ee 2-ends. Mo eo e , P is 3-connec ed o ype 32 R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 (8(P), ~,~(P)) and only 1-connec ed o ype (o~(P), g(P)). Clea ly, P sa is ies condi ion (a) bu no condi ion (b) in he analogue o Theo em 3.3. A simila example can be cons uc ed o condi ion (c). Fo F euden hal ends he wo-dimensional analogue o Theo em 1.13 also holds. Mo e explic ly, we ha e Theo em 3.8. Le P be an admissible in ini e 2-complex; hen he ollowing s a e- men s a e equi alen : (a) P is n-connec ed o ype (~(P), ~(P)). (b) Gi en any wo disjoin se s o F euden hal ends F = {~h ..... ~/q} and F' = {el .... , ep} and wo se s o posi i e in ege s {al,...,ap} and {d 1 ..... aq} wi h ~-~ =l ai = ~-'~qi=l a~. = n, he e exis n independen 2-bi ays om F o F' such ha ai o hem de ine ~i and a~ o hem de ine j, o all i, j. P oo . Clea ly only (a) ~ (b) needs o be checked. Fo his we obse e ha acco ding o P oposi ion 2.4 each F euden hal end ~E~-(P) de ines a closed se A~ =i,1(~)C ~(G(P)) whe e G(P) is he bipa i e g aph o P. The e o e he se s F and F' de e mine wo amilies ~'F and dE, o pai wise disjoin closed se s o F euden hal ends o G(P). As P is n-connec ed o ype (~(P),~(P)) i ollows ha P oposi ion 1.12 can be applied o dF and dF, in G(P) o show he exis ence o n disjoin bi ays in G(P) such ha ai o hem s a a A~, and bj o hem end a A~j. Mo eo e bi ays in G(P) can be ega ded as 2-bi ays in P ia he bijec ion g in P oposi ion 2.4 and now he diag am in P oposi ion 2.4 yields he esul . [] Rema k 3.9. We lea e o he eade he s a emen s and he p oo s o he co espond- ing heo ems o he connec i i y pai s (g(P),~(P)) and (~(P),~,~2(P)) by using P oposi ions 1.7 and 1.12, espec i ely. Appendix. Some ela ionships among he a ious connec i i y ypes He e we gi e some ela ionships among he a ious connec i i y o de s al eady de- ined o g aphs and 2-complexes in Sec ions 1 and 2, espec i ely. In his appendix we shall use he iden i y Sep(A,B)=Conn(A,B) p o ided by Theo ems 1.1 and 2.14 wi hou any u he commen . We shall s a wi h he esul s conce ning g aphs. Lemma A.1. Fo a g aph G he ollowin9 equali ies hold: (a) 50(V(G), V(G)) = 6¢(V(G), ~(G)). (b) / [~-(G)[~>2 hen 6¢(V(G),c~) _36¢(~(G),~(G))=~Sa(V(G),~(G)). P oo . (a) Le J E Sa(V(G), V(G)) be a cu -se o he e ices ,w E G. Le C~ and Cw be he connec ed componen s o , and w in G-J. I bo h C and Cw a e ini e he e R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 33 mus exis a hi d in ini e connec ed componen Coo since J is ini e. Then J sepa a es and w o any end e de ined by C~, and so J E 6¢(V(G), Y(G)). I C (Cw) is in ini e we p oceed in he same way wi h Cw = C~ (C~, = C~, espec i ely). We ha e shown ~(V(G), V(G)) C_ 5P(V(G),~(G)). Con e sely, i J sepa a es E V(G) o e E ~(G), i is ob ious ha J sepa a es o any e ex w E V~. (b) I J E 6~(~(G),J~(G)) hen J sepa a es wo ends e,e~E ~(G), and he e o e i sepa a es ~ om any e ex in he connec ed componen V,; C_ G- J which de- ines d. Hence, 6P(~-(G), W(G)) C_ ~(V(G), ~(G)). Mo eo e , i L E 6e(V(G), cxD) hen J lea es some e ex in a ini e connec ed componen C~, C_ G - L. The e o e, L sepa a es om he whole se ~(G), and so L E 6~(V(G),~(G)). Now i K E :T(V(G),~(G))- 6e(~(G),~(G)), K sepa a es an end e E J~(G) o a e ex E V(G) bu he connec ed componen C~, c_ G - K which con ains mus be ini e. The e o e K E.~(V(G),o~). Hence, equali y (b) holds. [] P oposi ion 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 ac , when [~(G)L >/2 we ha e Conn(V(G), ~(G)) -- min{Conn(V(G), oo), Conn(~(G), ~(G))}. Co olla y A.3. Conn(V(G), V ( G ) ) = Conn(V(G), ~,~ ( G ) ) is he smalles connec i i y o de o G. Mo eo e , o a one-ended g aph he connec i i y o de Conn(~-(G), ~(G)) is no de ined and he o he connec i i y o de s a e he same. P oo o P oposi ion A.2. The pa s (a) and (b) a e di ec consequences o Lemma A. 1. (c) Assume Sep(Y(G), ~(G)) = n < Sep(~(G), ~(G)). Then any J E 5a(V(G), ~(G)) wi h IJl=n does no belong o ~9~(~(G),~-(G)) and so JE6~(V(G),ac) by Lemma A.l(b). Hence Sep(V(G), c~)~<n, and by (b) we ge Sep(V(G), c~)--n. I Sep(V(G), ~(G)) = n < Sep(V(G), co), clea ly J ~ Sep(V(G), cx~) when IJI = n. The e o e J E ~9~(~(G), ~(G)) by Lemma A.l(b) and so Conn(~(G), ~(G))~<n, and (a) yields Conn(~(G), ~(G)) = n. [] The wid h o he end ~, w(e), is he maximum numbe o pai wise disjoin ays which de ine e. The numbe w(e) is a ained [7], and i is also called mul iplici y in [12]. The wid h o ~(G) is he numbe w(G)=min{w(e); e E ~(G)}. We can add o P oposi ion A.2 he ollowing p oposi ion whose p oo is immedia e. P oposi ion A.4. I w(G) and al(G) a e he wid h and alence o G, espec i ely, hen Conn(J~(G), ~(G)) <<.w(G) and Conn(g(G), cxz) ~< al(G). 34 1L Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 Rema ks. A.5. (1) The simple examples below show ha he P oposi ions A.2 and A.4 can be s ic . (a) c--i: 1 / inequali es 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 < al(G) = 3. (2) No ice ha o ixed alues al(G) and [~(G)[ i can be ound a bi a y la ge alues o Conn(~'(G),~(G)). We gi e an example wi h al(G)=2 = I~(a)l. Le C, be a cycle wi h n edges. Then he g aph G=C, × Y_U{ × ~; E V(C,)} e i ies Conn(~-(G), ~(G)) = n. Now we u n ou in e es o 2-complexes. Fo hem we ha e he ollowing. P oposi ion A.6. Any in ini e admissible 2-complex P wi h I~-(P)I ~>2 e i ies: (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 (i (P), ~(P)), w2(P)}. He e w2(P)=min{w(A),AE~2(P)} deno es he wid h o P and w(A) is he wid h o he 2-end A; i.e. he maximal numbe o independen 2- ays de ining he 2-end A. On he o he hand, i is clea ha Conn(g(P),cxz)~< al(P). Fu he mo e we can p o e P oposi ion A.7. Fo an in ini e admissible 2-complex P wi h [~2(P)[ I>2 he ollow- ing equali ies hold: (a) min {Conn (8(P), cx~), Conn (~2(P), ~2(P))} = Co m (g(P), J2(P)) =Conn (g(P), #(P)). (b) min{Conn(~(P), c~), Co m(i (P), ~-2(P))} = Conn(8(P), i (P)). R. Ayala e al. / Disc e e Ma hema ics 194 (1999) 13~7 35 Co olla y A.8. The numbe Conn(~(P), g(P)) = Conn(~(P), ~2(P)) is he smalles connec i i y o de o P. In addi ion, i P b an in ini e admissible 2-complex wi h only one 2-end hen all he connec i i y o de s de ined o P a e he same. The p oo o P oposi ions A.6 and A.7 need he ollowing lemmas in ol ing he amily o cu -se s 5~(A, B). Lemma A.9. Fo P as abo e we ha e: (a) o~(#(p), y(p)) C_ 6a(o (P), ,,~2(P)) = ~(o#(P), ~ (P)). (b) ~5,(~(°~-(P), Y(P)) c_ 6#(~(p), ~2(P))= ~(~2(P), ~2(P)). (c) ~(e(P), g(P)) = 5~(o~(P), i (P)) U 5~( 2(P), ~-2(P)). P oo . (a) Clea ly, i J sepa a es he edge e om he end e hen J sepa a es e om any 2-end A E h-l(e) (see P oposi ion 2.4). In o de o show he equali y in (a) we jus mimic he p oo o Lemma A.1 by using he iden i ica ion 2(P)= ~(G(P)) in P oposi ion 2.4. (b) I J sepa a es e and d in Y(P) hen J also sepa a es e (d espec i ely) o any 2-end A~E h-I(e ') (A E h-l(e) espec i ely). (c) The inclusion 6e(~2(P),~2(P))c 5P(eg(p), g(p)) ollows om P oposi ion 2.4 and he same p oo as in (A.l(a)), and so 5~(~2(P),~2(P))USc(g(P)),~(P))C_ 5¢(~(P),o (P)) by (a). Assume now J E 5P(g(P), g(P)). I J ~ 5P(8(P),~(P)) he complemen P- J has a leas wo 2-pa h connec ed componen s and all o hem a e in ini e, o he wise J would be a cu -se in 5¢(g(P)),,,~(P)). Hence J E 5~(Y2(P),~2(P)). I J ~ 5P(J2(P), ~2(P)) he complemen P - J has a leas wo 2-pa h componen s bu only one o hem can be in ini e. The e o e J ~ 5e(g(P), ~(P)). [] Lemma A.IO. Fo P as abo e we ha e (a) D(~(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)). P oo l (a) This ollows om he iden i ica ion ~-2(P)= ~(G(P)) in P oposi ion 2.4 and by he same p oo as in Lemma A. l(b). (b) Gi en a cu -se J o e E o~(P) and oe, i is clea ha J sepa a es e om any F euden hal end e E oj(p). Simila ly, gi en a cu -se J o e E o~(p) and A E o~2(P) we ha e ha J sepa a es e om any in e io e ex in he connec ed componen C j c_ P-J which de ines A. Mo eo e , i J E S#(~(P), o~(p)) - c (g(p), o~2(p)), j sepa a es an edge e E ~(P) o a F euden hal end e E o~(p), and by Lemma 2.1 e mus lie in a ini e connec ed componen o P -J. The e o e J E ~9°(¢(P), c~), and he i s equali y is p o ed. The second equali y is checked in a simila way. [] 36 R. Ayala e al./Disc e e Ma hema ics 194 (1999) 13-37 P oo o P oposi ion 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))}. Fu he mo e, i Conn(8(P), 8(P)) = n < Conn(¢(P), ~,~(P)), by Theo em 2.14 he e ex- is s a cu -se J E ~(6~(P), 8(P)) wi h l J[ = n. In pa icula , 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 o show Conn(6~(P), ~-(P)) ----- n. (b) By using Lemmas A.9(b) and A.10(b) one ge s Conn(~2(P),~2(P))~<Conn (~(P), ~-2(P)) ~< Conn(o~(P), ~(P)) and Co m(e(P), #-(P))-<< Conn(~(P), ~2(P)). Finally, one easily checks Conn(~-(P),~2(P))<~w2(P). [] P oo o P oposi ion A.7. (a) He e we ollow he same a gumen s as in he p oo o A.2(c) by using Lemmas A.9(a), (c) and A.10(a). (b) I ollows he same pa e n as he p oo o A.2(c) by using now A.10(b). [] Example A.11. The ollowing admissible 2-complex P shows ha he inequali ies in P oposi ion A.6 can be s ic . Le X be as in Example 2.3 and le X' be he symme ic copy o X wi h espec o he axis OY. We conside he space Y -- [-2, -1] × [-4,4]U X UX' U [-1,2] × ([2,4] U [-4, -3]). Then P is he admissible 2-complex ob ained as a subdi ision o he ollowing cellula decomposi ion o X wi hou new e ices: y = We ha e Conn(8(P), ~-(P)) = Conn(~2(P), ~2(P)) = 1, Conn(Y(P), ~-2(P)) = 2 and Conn(~(P), ~-(P)) = w2(P) = 3. Acknowledgemen s This wo k was pa ially suppo ed by he p ojec DGICYT PB96-1374. Re e ences [1] D. Ba ne e, Decomposi ions o homology mani olds and hei g aphs, Is ael J. Ma h. 41 (1982) 203-212• [2] G. Di ac, Connec edness and s uc u e in g aphs, Rend. Ci culo Ma . Pale mo 9 (1960) 114-124. R. Ayala e al./ Disc e e Ma hema ics 194 (1999) 13-37 37 [3] G. Di ac, Ex ensions o Menge 's heo em, J. London Ma h. Soc. 38 (1963) 148-163. [4] H. F euden hal, U-be die opologische Raiime und G uppe , Ma h. Z. 33 (1931) 692-713. [5] R. Halin,/,]-be T ennende Eckenmenge in G aphen und de Menge schen Sa z, Ma h. Ann. 157 (1964) 34-41. [6] R. Halin, Zu Theo ie de n- ach Zusammenhangenden G aphe, Abh. Ma h. Sem. Uni . Hambu g 33 (1969) 133-14. [7] R. Halin, Die Maximalzahl emde zweisei ig nnendliche Wege in G aphen, Ma h. Nach. 44 (1970) 119-127. [8] R. Halin, A No e on Menge 's Theo em o In ini e Locally Fini e G aphs, Abh. Ma h. Sem. Uni . Hambu g 40 (1974) 111-114. [9] D. K6nig, Theo y o Fini e and In ini e G aphs, Bi khaiise , Basal, 1990. [10] D.R. Linck, Cha ac e iza ion o n-connec ed and n-line connec ed g aphs, J. Combin Theo y Se . B 14 (1973) 122-124. [11] K. Menge , Zu allgemeinen Ku en heo ie, Fundam, Ma h. 10 (1927) 96-115. [12] N. Pola , Topological aspec s o in ini e g aphs, in: G. Hahn, G. Sabidussi, R.E. Wood ow (Eds.), Cycles and Rays, Ma hema ical and Physical Sciences, ol. 301, Kluwe , Do d ech , 1990. [13] H. Whi ney, Cong uen g aphs and he connec i i y o g aphs, Ame . J. Ma h. 54 (1932) 150-168. [14] EY. Woon, n-Connee edness in pu e 2-complexes, Is ael J. Ma h. 52 (1985) 177-192.