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.