a Xi :1507.03975 2 [ma h.CO] 15 Jul 2015
Gene a ing amilies o su ace iangula ions. The case o
punc u ed su aces wi h inne deg ee a leas 4
Ma ´ıa-Jos´e Ch´a ez∗Seiya Negami †An onio Quin e o ‡
Ma ´ıa T inidad Villa §
Abs ac
We p esen wo e sions o a me hod o gene a ing all iangula ions o any punc u ed
su ace in each o hese wo amilies: (1) iangula ions wi h inne e ices o deg ee ≥4
and bounda y e ices o deg ee ≥3 and (2) iangula ions wi h all e ices o deg ee ≥4.
The me hod is based on a se ies o e e sible ope a ions, e med educ ions, which lead o
a minimal se o iangula ions in each amily. Th oughou he p ocess he iangula ions
emain wi hin he co esponding amily. Mo eo e , o he amily (1) hese ope a ions
educe o he well-known edge con ac ions and emo als o oc ahed a. The main esul s
a e p o ed by an exhaus i e analysis o all possible local con igu a ions which admi a
educ ion.
Keywo ds: punc u ed su ace, i educible iangula ion, edge con ac ion, e ex
spli ing, emo al/addi ion o oc ahed a.
This wo k has been pa ially suppo ed by PAI FQM-164; PAI FQM-189; MTM 2010-
20445.
1 In oduc ion
By a iangula ion o a su ace F2we mean a simple g aph G(i.e., a g aph wi hou loops
and mul iple edges) embedded in F2so ha each ace is bounded by a 3-cycle and any
wo aces sha e a mos one edge. In o he wo ds, he e ices, edges and aces o G( he
co esponding se s deno ed by V(G), E(G) and F(G), espec i ely) o m a simplicial complex
whose unde lying space is F2. Two iangula ions Gand G′o F2a e equi alen i he e is
a homeomo phism ϕ:F2→F2wi h ϕ(G) = G′. In his pape su aces a e supposed o
be compac and connec ed and possibly wi h bounda y. Su aces wi hou bounda y will be
e med closed su aces. He e, we dis inguish be ween iangula ions only up o equi alence.
Gene a ion om i educible iangula ions o a su ace F2is a well-known p ocedu e
o ob aining all he iangula ions o F2. Recall ha an edge o a iangula ion Go F2
is con ac ible i he e ices o he edge can be iden i ied (mul iple edges a e emo ed, i
hey appea ) and he esul is s ill a iangula ion o F2([2]). A iangula ion is said o
∗Depa amen o de Ma em´a ica Aplicada I, Uni e sidad de Se illa, Spain, mjcha [email protected]
†Resea ch Ins i u e o En i onmen and In o ma ion Sciences, Yokohama Na ional Uni e si y, 79-2 Toki-
wadai, Hodogaya-Ku, Yokohama 240-8501, Japan, [email p o ec ed]p
‡Depa amen o de Geome ´ıa y Topolog´ıa Uni e sidad de Se illa, Spain, quin[email p o ec ed]
§Depa amen o de Geome ´ıa y Topolog´ıa, Uni e sidad de Se illa, Spain, [email p o ec ed]
1
be i educible i i has no con ac ible edge. I educible iangula ions o m a gene a ing se
o all iangula ions o he same su ace in he sense ha e e y iangula ion o he su ace
can be ob ained om some i educible iangula ion by a sequence o e ex spli ings ( he
in e se o he edge con ac ion ope a ion); see [2].
Ba ne e and Edelson [2] showed ha e e y closed su ace has ini ely many i educible
iangula ions. Mo e ecen ly, Boulch, Colin de Ve di`e e, and Nakamo o [4] showed he same
esul o compac su aces wi h a nonemp y bounda y. No wi hs anding, i is a om
being i ial o enume a e he i educible iangula ions o a gi en su ace. Comple e lis s o
i educible iangula ions a e a ailable only o some low genus su aces. See [20], [22], [23]
o a comp ehensi e e e ence o he class o closed su aces.
So a , he esea ch on i educible iangula ions o closed su aces has p oduced a con-
side able li e a u e. This is no he case o su aces wi h bounda y, o which ew e e ences
can be p esen ly ound; see [4], [8]. This pape is a con ibu ion o he s udy o i educible
iangula ions o punc u ed su aces (i.e., su aces wi h a hole p oduced by he dele ion o
he in e io o a disk in closed su aces).
I is well known ha any i educible iangula ion Go an a bi a y non-sphe ical closed
su ace F2has minimum deg ee ≥4 [20]. This is no longe ue i F2has non-emp y
bounda y. Howe e , i a bounda y e ex has deg ee 2 hen lies in exac ly one ace o G
whose bounda y edges a e i ially con ac ible (unless G educes o a iangle). The e o e
we will deal exclusi ely wi h iangula ions wi h minimum deg ee ≥3. No ice ha his
condi ion implies ha no ace sha es mo e han one edge wi h he bounda y o he su ace.
This way, all i educible iangula ions o a su ace wi h bounda y F2(o he han he disk)
a e elemen s o he class F2
◦(4) consis ing o all iangula ions o F2wi h minimum deg ee
≥3 and deg( )≥4 o all e ices missing he bounda y.
In his pape we gi e a gene a ing heo em o such iangula ions in e ms o in e nal
ope a ions in he class F2
◦(4); ha is, we show ha all iangula ions o a punc u ed su -
ace o he han he disk can be educed o an i educible iangula ion by pe o ming such
ope a ions (Theo em 18). The pa icula case o he disk is also ea ed (Theo em 19).
Simila ly, we in oduce a se o in e nal ope a ions in he sub amily F2(4) ⊆ F2
◦(4)
consis ing o all iangula ions wi h minimum deg ee ≥4. In con as wi h he case o closed
su aces, o a su ace wi h non emp y bounda y, he minimal iangula ions ob ained by he
use o such ope a ions may con ain con ac ible edges whose con ac ion p oduce 3- alen
e ices. We p o e ha such con ac ible edges a e necessa ily loca ed in wo pa icula
con igu a ions gi en in De ini ions 4 and 34, see Theo em 38.
The main esul s collec ed in his wo k can be ega ded as ex ensions o punc u ed su aces
o he main heo ems by Nakamo o and Negami o closed su aces in [17].
2 No a ion and p elimina ies
I Gis a iangula ion o he su ace F2, le ∂G ⊂Gdeno e he subg aph iangula ing he
bounda y ∂F2. The e ices and edges o ∂G will be called bounda y e ices and bounda y
edges o G, espec i ely. The e ices and edges o G−∂G will be called inne e ices and
inne edges o G, espec i ely. Le us now ecall ha he link o a e ex x∈G, deno ed
link(x), is he se o edges in Gwhich join ly wi h he e ex x o m a iangle in G.
Le e= 1 2be an edge in G. Le us ecall ha he dis ance om e o ∂G, deno ed
2
d(e, ∂G), is de ined o be he minimum numbe o edges needed o connec eand ∂G. The
esul ing g aph ob ained by con ac ing ein Gis deno ed by G/e. The con ac ion o a
pai o disjoin edges in wo adjacen aces in Gis named double con ac ion. I e= 1 2
is a con ac ible edge o G, hen he new e ex = 1= 2in G/e sa is ies deg( ) =
deg( 1) + deg( 2)−3 when eis a bounda y edge o G, and deg( ) = deg( 1) + deg( 2)−4
o he wise. He e deg( ) deno es he deg ee o he e ex , i deg( ) = kwe say ha is a
k- alen e ex. A 3-cycle in Gis c i ical i i consis s o h ee edges which do no bound a
ace o G. Besides, i x 1 2is a ace o G, hen deg(x) diminishes by one a e he con ac ion
o e.
When a lowe bound k o he deg ee o he e ices is p ese ed a e con ac ions we
will use he e m k-con ac ion. Namely, gi en a iangula ion Gwi h minimum deg ee ≥k,
an edge eis said o be k-con ac ible (kc-edge o sho ) i he minimum deg ee o G/e is a
leas k. I an edge eis con ac ible bu no k-con ac ible, we call e o be a cnkc-edge, o
sho . The in e se ope a ion o he con ac ion o he edge e= 1 2is he spli ing o 1= 2.
When deg( i)≥k o i= 1,2, a e he spli ing, his will be called a k-spli ing.
Rema k 1.No ice ha he con ac ion o an edge e∈Gbelonging o a c i ical 3-cycle
p oduces a double edge. On he o he hand, i ebelongs o no c i ical 3-cycle and a mos
one o i s end e ices belongs o ∂G, hen eis con ac ible. In o he wo ds, he impedimen s
o he con ac ibili y o ea e he wo ollowing loca ions o ein G:
(1) ebelongs o a c i ical cycle o G. This is he case i elies on he bounda y o a hole o
leng h 3.
(2) eis an inne edge bu i s wo e ices belong o ∂G.
Rema k 2.No ice ha a necessa y condi ion o an in e io edge e= 1 2 o be 4-con ac ible
is ha ebelongs o aces 1 2 3and 1 2 4so ha deg( i)≥5 o i= 3,4. I eis a
bounda y edge lying in a ace 1 2 3, he necessa y condi ion o e o be 4-con ac ible is
ha deg( 3)≥5.
The ollowing de ini ions ex end o su aces wi h bounda y he one gi en in [17] o closed
su aces.
De ini ion 3. Le Gbe a iangula ion o a su ace F2possibly wi h non-emp y bounda y.
Le 1 2 3be a cycle o Gsuch ha deg( i) = 4 o i= 1,2,3 and {a1, a2, a3}be he only
h ee e ices such ha aiis adjacen o jand k o {i, j, k}={1,2,3}. The subg aph
H⊂Ginduced by he e ex se {a1, a2, a3, 1, 2, 3}is said o be an oc ahed on componen
cen e ed a 1 2 3wi h emaining e ices a1, a2, a3i he cycle a1a2a3exis s in G(and hence
in H) and one o he ollowing condi ions holds:
1. i/∈∂G o all i= 1,2,3.
2. Only one ilies in ∂G and ∂G coincides wi h iajak.
3. Exac ly i, j∈∂G and hence ∂G = i jak.
4. i∈∂G o all i= 1,2,3 and hence ∂G = i j k.
An oc ahed on componen o Gis said o be ex e nal i wo edges aiaj,ajaklie in ∂G (in
pa icula , δ(aj) = 4). Obse e ha his happens only unde condi ion 1.
3
a3
a1
a2
2
1
3
O
∂G
3
a1
a2
2
1
b
O
∂G
3
a1
a2
2
1
a3
b
O
∂G
a3
a3
a1
a2
1
3
O
2
∂G
a3
a1
a2
1
3
O
2
∂G
a3
a1
a2
1
3
O
2
∂G
a3
a1
a2
2
1
3
O
Figu e 1: Oc ahed on and quasi-oc ahed on componen s in G.
De ini ion 4. The subg aph Hin De ini ion 3 will be e med a quasi-oc ahed on componen
o Gcen e ed a 1 2 3and emaining e ices a1, a2, a3i one o he ollowing condi ions
holds. (Figu e 1).
1. The cycle a1a2a3exis s bu does no de ine a ace in Gand only one e ex ibelongs
o ∂G bu (in con as wi h 2 abo e) ajak/∈∂G.
2. Only he edge aiaj ails in closing he cycle a1a2a3in G, hence k∈∂G and all he
3-cycles o Ha e aces o G.
Rema k 5.No ice ha he possible occu ences o he subg aph Ho he han he ones
conside ed in De ini ions 3 and 4 appea when a leas wo edges aiajdo no exis in G(and
hen k∈∂G). I no edge aiajexis s in G, hen H=Gis a iangula ion o he disk. On
he o he hand, i only one edge aiajis in G, hen akhas deg ee 2 in ∂G.
No a ion: Oc ahed on and quasi-oc ahed on componen s will be deno ed Oand
b
O, espec-
i ely.
Rema k 6.Le us ema k also ha a mos one 3-cycle o an oc ahed on componen o G
may no be a ace o G. In such case, ∂G educes o ha 3-cycle.
Le us no e ha o a quasi-oc ahed on componen o G he edge ai 3is always a bounda y
edge o G, o i= 1,2.
No ice ha no quasi-oc ahed on componen
b
Ocan be ex ended o an oc ahed on com-
ponen . Indeed, i i∈
b
O ∩ ∂G, hen he 3-cycle a1a2a3is no a ace e en hough he edge
ajakopposi e o iexis s (and i is necessa ily an inne edge).
3 Cha ac e izing he iangula ions o inne deg ee a leas 4.
I is well known ha any i educible iangula ion o a closed su ace o he han he sphe e
has minimum deg ee ≥4. The e o e i educible iangula ions o punc u ed su aces F2
(o he han he disk) mus ha e minimum inne deg ee ≥4 ( ha is, only bounda y e ices
a e allowed o ha e deg ee 3); ha is, hey a e in he class F2
◦(4) de ined abo e.
4
In his sec ion we gi e a me hod o cons uc all iangula ions in F2
◦(4) om i educible
ones by ope a ions which keeps all iangula ions wi hin his class (Theo em 18). The special
case o he disk is also conside ed (Theo em 19). This way we gene alize Theo ems 1 and
2 in [17]. The me hod in [17] is based on he use o 4-spli ing and adding oc ahed a. The
exis ence o 3- alen e ices in he bounda y equi es wo u he ope a ions: adding lags
and iode 3-spli ings.
Th oughou his sec ion F2will deno e a su ace wi h connec ed (possibly emp y) bound-
a y. Recall ha G∈ F2
◦(4) deno es an a bi a y bu ixed iangula ion o F2wi h all i s
inne e ices o deg ee ≥4.
Le us s a by ixing some no a ion.
No a ion: I xis a e ex o Gwi h deg(x) = 4 we ix no a ion by calling x1, x2, a, b i s
neighbou s and o he sake o simplici y link(x) is w i en link(x) = x1abx2x2x1i x /∈∂G
o link(x) = x1abx2i x∈∂G. This no a ion will be used h oughou his pape wi hou
any u he commen .
x
A emo able lag
x
x2
A non emo able lag (x1 is a 4c-edge)
x1
b
a
x2
∂G ∂G
a
b
x1
x
ab inne edge,
xinne e ex
ab bounda y edge,
xinne e ex
a
aa
a
a
a
b
bb
b
b
b
b
x
x
x
x
x
x1
x1
x1
x1
x1
x1
x2
x2
x2
x2
x2
x2
y
y
∂G ∂G ∂G
∂G
∂G ∂G
∂G
a∈∂G,xand b
inne e ices.
a, x ∈∂G,
binne e ex.
ab inne edge,
x∈∂G
ab bounda y edge,
x∈∂G
Figu e 2: Di e en con igu a ions o link(x), wi h deg(x) = 4 and dis ance ≤1 om ∂G.
5

The e ices o deg ee 3 in ∂G play a c ucial ole in he amily F2
◦(4). We will gi e hem
a special name.
De ini ion 7. Gi en G∈ F2
◦(4),a bounda y e ex o deg ee 3 is called a iode o G. A
con ac ible edge o Gis said o be a iode de ec ing edge i he e ices o deg ee 3 p oduced
by i s con ac ion a e iodes.
Rema k 8.Fo e e y ace abx such ha ab is a con ac ible bounda y edge, xlies in he
bounda y and degh(x) = 4 i eadily ollows om De ini ion 7 ha ab is a iode de ec ing
edge.
On he o he hand, he con ac ion o any inne iode de ec ing edge p oduces a mos
h ee iodes since any con ac ion modi ies he deg ee o a mos h ee e ices.
I is also eadily checked ha wo adjacen iodes de ine a con ac ible edge in ∂G, say
ab, unless Gis isomo phic o he comple e g aph K4(and so G iangula es he disk). I , in
addi ion, ab sha es a ace wi h a 4- alen inne e ex, he con ac ion o any edge inciden
a xo in link(x) is allowed in F2
◦(4), bu ab is a cn4c−edge. To ge id o his obs acle, we
de ine he ollowing con igu a ion e med lag. Recall ha a e ex is said o be independen
o deg ee ki all neighbo s o ha e deg ee 6=k.
De ini ion 9. Gi en G∈ F2
◦(4),le xbe an independen inne e ex o deg ee 4 such
ha link(x) = x1abx2x1 e i ies {x1a, ab, bx2} ⊂ ∂G,x1x2∩∂G ={x1, x2},and deg(a) =
deg(b) = 3. The subg aph induced by {x, x1, x2, a, b}is called a lag cen e ed a x. I he
g aph G′=G− {a, b, x} emains in F2
◦(4), he lag is said o be emo able (see Figu e 2).
Con e sely, we say ha Gis ob ained om G′by adding a lag along a bounda y edge o
G′.
Rema k 10.Obse e ha any lag is emo able unless deg(x1) = 4 (o deg(x2) = 4) and his
is he only impedimen o a lag o being emo able. I a lag is non- emo able hen ei he
x1 o x2 is a bounda y 4c-edge.
The nex lemma ollows immedia ely om de ini ions and i will be used in he p oo o
Theo em 18 below.
Lemma 11. Le ab be a con ac ible inne edge o G∈ F2
◦(4),le xand ybe e ices so ha
xis a bounda y e ex wi h deg(x) = 4 and abx and aby de ine wo aces o G. Then ab is
a iode de ec ing edge whene e yis a bounda y e ex o deg(y)≥4o else yis an inne
e ex o deg ee deg(y)≥5.
Nex de ini ions in oduce he amily o emo able oc ahed on componen s, which added
o 3-con ac ions and 4-con ac ions o edges lead o a minimal class o i educible iangu-
la ions o any punc u ed su ace in he spi i o Nakamo o and Negami’s heo em in [17].
Recall he no a ion in De ini ion 3.
De ini ion 12. We will say ha an oc ahed on componen Oin a iangula ion G∈ F2
◦(4)
is emo able in F2
◦(4) i he g aph G′=G− { 1, 2, 3} emains in F2
◦(4). We also say ha
G′is ob ained by emo ing he oc ahed on O om G. Con e sely, Gis ob ained om G′
by adding an oc ahed on.
Rema k 13.I G∈ F2
◦(4) has an oc ahed on componen O, hen no edge o Ois 4-con ac ible
(see Rema k 2). Howe e , emo ing he inne se o e ices { 1, 2, 3}is equi alen o h ee
6
consecu i e edge 3-con ac ions ( 1a2, 2a3and 3a1, o ins ance). The e o e, we can ega d
his se o 3-con ac ions as a single ope a ion wi hin he class F2
◦(4) excep in case ha O
is ex e nal.
F om De ini ion 12, he ollowing esul gi es us su icien condi ions o an oc ahed on
being emo able.
Rema k 14.An oc ahed on componen Ois emo able in G∈ F2
◦(4) when any o he ollowing
cases holds:
•All e ices a1, a2, a3, ha e deg ee ≥6.
•A leas one o he e ices {a1, a2, a3}lies in ∂G and i s deg ee is equal o 5. Obse e
ha a leas one bounda y e ex o deg ee 3 appea s a e he emo al o O.
On he o he hand, i Odoes no hi ∂G and deg(ai) = 5 o some i∈ {1,2,3}, hen O
is no emo able bu he edge ai is 4c-edge whe e is he only neighbou o aiou side O.
Obse e ha ex e nal oc ahed a a e con igu a ions wi h many e ices and edges which
a e no ele an om he opological poin o iew. We le hem o be dele ed acco ding o
he ollowing de ini ion.
De ini ion 15. Le Obe an ex e nal oc ahed on componen in a iangula ion G∈ F2
◦(4).
I he g aph G′=G− {aj, i, i = 1,2,3} emains in F2
◦(4), Ois said o be edundan (see
Figu e 3). Con e sely, we say ha Gis ob ained om G′by adding an oc ahed on along a
bounda y edge o G′.
Remo able oc ahed on
1
2
3
Non- edundan oc ahed on
Redundan oc ahed on
a1
a2
Figu e 3: Di e en ypes o oc ahed a in iangula ions o he M¨obius s ip. He e he su ace
is ep esen ed by a ec angula un olding wi h he opposi e e ical sides iden i ied in he
usual way.
No ice ha a e dele ing any edundan oc ahed on componen , he new iangula ion;
ha is G′=G− {aj, i, i = 1,2,3}, emains in F2
◦(4). Al e na i ely one can ega d he
dele ion o a edundan oc ahed on componen Oas he composi e o he olding o Oin o a
ace (as in De ini ion 22 below) and he emo al o he olded oc ahed on componen acco ding
De ini ion 12
Rema k 16.Any addi ion o an oc ahed on in De ini ions 12 and 15 is equi alen o apply
h ee consecu i e spli ings in an app op ia e se o e ices.
Thus, i Gis a iangula ion o any su ace F2con aining an oc ahed on componen O,
hen Gis educible. I su ices o check ha he in e io edges i jand ai jo Oin Figu e
1 a e con ac ible.
7
No ice ha by con ac ing he h ee edges i jo he iangula ion on he igh -hand side
o Figu e 3, we ob ain ano he iangula ion o he M¨obius s ip, depic ed wi h hin lines.
Rema k 17.An ex e nal oc ahed on Ois no edundan whene e deg(aj) = 5 o some j∈
{1,2,3}and his is he only impedimen o being edundan . This p o ides a iangle ajak
wi h a bounda y 4c-edge aj(see Figu e 3). A e con ac ing aj wo possible si ua ions
appea :
(i) Obecomes edundan .
(ii) O emains non- edundan .
In case (ii), a new bounda y 4c-edge ′ajappea s whose con ac ion leads us again o
case (i) o (ii). By i e a ing his p ocedu e, O eaches si ua ion (i) in ini ely many s eps.
O he wise G educes o O, and so G iangula es he disk.
Nex we p esen he main heo ems o his sec ion.
Theo em 18. E e y iangula ion G∈ F2
◦(4),o a punc u ed su ace F2, excep he disk,
can be ob ained om an i educible iangula ion o F2by a sequence o 3-spli ing iodes,
addi ions o lags, 4-spli ings and addi ions o oc ahed a.
Theo em 19. E e y iangula ion G∈ F2
◦(4) o he disk can be ob ained om a lag o an
oc ahed on componen by a sequence o 3-spli ing iodes, addi ions o lags, 4-spli ings and
addi ions o oc ahed a.
The p oo s o hese esul s a e consequence o he ollowing echnical lemma which deals
wi h he possible con igu a ions nea he bounda y. This is he c ucial di e ence wi h he
o dina y case o closed su aces s udied in [17].
Lemma 20. Assume ha ab is a cn4c-edge in G, ha is, he e is a ace abx in Gwi h
deg(x)≤4.
1. Le G∈ F2
◦(4) be a iangula ion o a punc u ed su ace di e en om he disk. I
d(ab, ∂G)≤1, hen ei he a 4c-edge o a subg aph H⊆Gin he amily
A={oc ahed on componen , iode de ec ing edge, lag}
can be ound a dis ance a mos 1 om ab.
2. I G iangula es he disk, hen he subg aph G′may educe o a lag o an oc ahed on.
Fo he sake o simplici y we will gi e he p oo o Lemma 20 in he inal appendix.
Rema k 21.I is s aigh o wa dly checked ha an oc ahed on componen Ois no con-
ac ible o a lag wi hin he amily F2
◦(4); ha is, any con ac ion o any inne edge in O
p oduces an inne 3- alen e ex. Hence, lags and oc ahed a a e needed o gene a ing all
iangula ions wi h minimum inne deg ee 4.
P oo o Theo ems 18 and 19. We will show ha o any educible iangula ion G∈
F2
◦(4),e e y cn4c-edge which is no a iode de ec ing edge lies in a emo able oc ahed on
o in a emo able lag. This way, an i educible iangula ion G′can be ob ained ecu si ely
8
om G. Con e sely, Gis cons uc ed om G′by a sequence o 3-spli ing iodes, addi ions
o lags, 4-spli ings and addi ions o oc ahed a.
Assume Gcon ains nei he 4c-edges no iode de ec ing edge. Since Gis educible, le
ab be a cn4c-edge in Gand he e o e, a e ex xwi h deg(x)≤4 de ines a ace abx o Gand
x1abx2⊆link(x) ( he edge x1x2may exis o no ). Le us ema k ha he case d(ab, ∂G)≥2
admi s he same kind o a gumen s gi en in Lemma 1 o [17] o closed su aces o ind ei he
an oc ahed on o a 4c-edge. Hence, we ocuss on he case d(ab, ∂G)≤1. In ha case Lemma
20 leads us o one o he ollowing cases:
(a) The e exis s a lag Xsuch ha d(ab, X)≤1, he e o e Xis emo able (o he wise a
4c-edge exis s acco ding o Rema k 10).
(b) The e exis s an oc ahed on componen Osuch ha d(ab, O)≤1, hus Ois emo able
o edundan in F2
◦(4) (see Rema ks 14 and 17). This inishes he p oo .

4 On educ ions o iangula ions o deg ee a leas 4.
Hence o h, unless o he wise is s a ed, by F2we mean any punc u ed su ace.
Recall ha F2(4) deno es he se o iangula ions o he su ace F2wi h all i s e ices o
deg ee ≥4. In his sec ion we gi e a se ies o educ ions in ol ing exclusi ely iangula ions
in F2(4). The wo ope a ions in oduced by Nakamo o and Negami in [17] a e among such
educ ions and hey a e he only ones which a e de ined in absence o bounda y. In pa icula ,
he iangula ions o closed su aces which a e minimal o such educ ions coincides wi h he
i educible iangula ions in [17]. In sha p con as wi h he class o closed su aces, o a
su ace wi h non emp y bounda y, he minimal iangula ions ob ained by such educ ions
may con ain con ac ible edges whose con ac ion p oduce 3- alen e ices. Fo his case,
we p o e in Theo em 38 ha hose possible con ac ible edges a e loca ed in wo pa icula
con igu a ions gi en in De ini ions 23 and 34 below.
No ice ha De ini ions 12 and 15 es ic o he amily F2(4) in he ob ious way so ha
emo able and edundan oc ahed a as well as emo ing and addi ion o such con igu a ions
a e de ined in F2(4). Besides hese ope a ions, we in oduce new ones in De ini ions 22, 23,
25 and 28 below.
De ini ion 22. Le G∈ F2(4) be a iangula ion o he su ace F2. Le Obe an ex e nal
oc ahed on o Gso ha deg(a3) = 4 and deg(ai) = 6 o i= 1 o 2. Le be a e ex o G
such ha a1a2 is a ace o G. By olding he oc ahed on Oon o he ace a1a2 we mean he
emo al o O ollowed by he addi ion o an oc ahed on o he ace a1a2 (Figu e 4). The
in e se ope a ion is called un olding an oc ahed on wi h espec o he bounda y o G.
De ini ion 23. Le G∈ F2(4) be a iangula ion o F2. A quasi-oc ahed on componen o
G,
b
O, is said o be emo able in F2(4) (o 4- emo able, o sho ) i one o he ollowing
condi ions holds:
1. The g aph G′=G− { 1, 2, 3}yields a iangula ion o F2in F2(4).
9
1
5
1
2
231
5
1
3
T2
b
x2
x2
x1
p
pp
p
x1
x1x2
x2
a
b
x
T2
qq
q
Figu e 14: A iangula ion o he punc u ed double o us wi h p ecisely one M-componen
cen e ed a abx and one non- emo able quasi-oc ahed on. He e ∂G =x1xx2qbap x1. The
cons uc ion is done in a simila way as in Figu e 13.
We a e now eady o es ablish and p o e he main esul o his sec ion. Namely,
Theo em 38. A iangula ion G∈ F2(4) o he su ace F2, di e en om he disk, is 4-
minimal i and only i each con ac ible edge (i any) o Gis loca ed in ei he a non- emo able
quasi-oc ahed on componen o an M-componen .
Theo em 39. The only 4-minimal iangula ion o he disk is he oc ahed on.
In o de o p o e Theo ems 38 and 39 we will need he ollowing echnical lemmas.
Lemma 40. Le G∈ F2(4) be a iangula ion o he su ace F2di e en om he disk.
Assume in addi ion ha Gcon ains a non-4- emo able oc ahed on componen , O, hen exac ly
one o he ollowing s a emen s hold:
1. The e is a leas one 4c-edge ai wi h ai∈ O, /∈ O and O u ns o be 4- emo able
a e con ac ing ai .
2. ∂G ∩V(O)⊆ {a1, a2, a3}and his in e sec ion con ains a leas wo e ices ai, aj.
P oo . Since Ois non- emo able, Ohas an ex e nal e ex, say a1, such ha deg(a1) = 5.
Le us suppose ha Odoes no in e sec he bounda y, hen a1/∈∂G,deg(a2), deg(a3)≥6.
Hence he e is an edge a1 in G−E(O) exis ing he wo aces a1a2and a1a3in G. This
way, a1 is a 4c-edge. A e con ac ing i , deg(a1) inc eases and he oc ahed on u ns o be
4- emo able.
Mo eo e , i he in e sec ion V(O)∩∂G educes o a single e ex, le us suppose ha his
in e sec ion is p ecisely he e ex a2. Since no edge aiajlie in ∂G hen deg(a2)≥6 holds
and since Ois non- emo able, deg(ai) = 5 o i= 1 o i= 3. Le us suppose deg(a1) = 5 and
le be he bounda y e ex adjacen o a2and a1. The e o e a1a2and a1a3a e aces o
G, and since a1is no a bounda y e ex, i eadily ollows ha a1 is a 4c-edge o G. Again,
a e con ac ing i , he oc ahed on become 4- emo able. The e o e, ∂G ∩V(O) con ains a
leas wo e ices ai, aj.
In he ollowing lemma we will use he ope a ions Riin Table 1.
16

x
x1x2
x1
x2ab
pq
w
ax1
pqx2b
p
b
p
q
M4
q
q
M4
z
M4
p
q
M4
w
w
z
z
Figu e 15: Obse e ha δ(a) = 5, δ(b)≥6, δ(x2)≥6, δ(x1)≥6.
Lemma 41. Le G∈ F2(4) be a iangula ion o he su ace F2, and le Obe a non- emo able
oc ahed on componen o Gwi h a leas wo e ices ai, ajin ∂G. Then
1. I E(O)∩∂G ={a1a2}and deg(a2) = 5, hen, he e is p ecisely one e ex ∈
link(a2)−V(O)and by applying an ope a ion R5 o G, he new iangula ion G′belongs
o F2(4).
2. I E(O)∩∂G ={a2a3, a1a3}and δ(a1) = 6 o δ(a2) = 6, hen by applying an ope a ion
R3 o G, he new iangula ion G′belongs o F2(4).
3. I E(O)∩∂G =∅, hen he e exis s p ecisely one e ex ajsuch ha deg(aj) = 5 and
he e is a 4c-edge inciden wi h aj.
P oo . I is s aigh o wa dly deduced om he de ini ions in ol ed in he s a emen s and
Lemma 40 (2). Obse e ha V(O)∩∂G ={a1, a2, a3}implies ha Ois 4- emo able.
As a consequence o Lemmas 40 and 41 we ge
Co olla y 42. Any oc ahed on componen o a iangula ion in F2(4) o he su ace Fcan
be dele ed by one o he educ ions R1,R2,R3o R5o Table 1.
The ollowing is he co esponding analogue o Lemma 20 o he class F2(4).
Lemma 43. Le G∈ F2(4) be a iangula ion o he su ace F2. I ab is a cn4c-edge in G
so ha d(ab, ∂G)≤1, hen one o he ollowing con igu a ions can be ound a dis ance a
mos 1 om ab:
17
1. A 4c-edge
2. A subg aph in he amily
B={oc ahed on componen ,quasi-oc ahed on componen , N−componen }
3. An M-componen cen e ed a abx.
The p oo o Lemma 43 is a specializa ion o he p oo o Lemma 20 and i will be
pos poned o he inal appendix.
P oo o Theo ems 38 and 39: Le ab a con ac ible edge in G. As Gis 4-minimal,
ab is a cn4c-edge. Mo eo e , i d(ab, ∂G)) ≥2 hen he same a gumen s gi en in Lemma 1 o
[17] o closed su aces allows us o ind a 4c-edge o an oc ahed on componen a dis ance
≤1 om ab. This con adic s he 4-minimali y o G. Thus, necessa ily, d(ab, ∂G)≤1 and
Lemma 43, Co olla y 42 and, again, he 4-minimali y o Gyield ha ab lies in a non- emo able
quasi-oc ahed on componen o an M-componen .
Con e sely, i he con ac ible edge ab belongs o a non- emo able quasi-oc ahed on com-
ponen
b
O hen i is no a 4c-edge since
b
Odoes no con ain such edges by Rema k 13. Mo e-
o e ,
b
Ocanno be ex ended o an oc ahed on in Gby Rema k 5. Finally, no N-componen
con ained in
b
Ocan be educed by Rema k 29. Hence, no educ ion Rican be applied o
emo e ab.
On he o he hand, i ab belongs o an M-componen M ⊂ G, we know by P oposi ion
37 ha Mis s able unde educ ions Ri(i= 1,...,6). This inishes he p oo o Theo em
38.
Le us conside he case o he iangula ed disk. F om Rema k 36 no M-componen may
appea in a iangula ion o he disk. Besides, a quasi-oc ahed on componen
b
Owill be always
emo able acco ding o De ini ion 23. In ac , i is clea ha he deg ee ≥4 condi ion expels
he quasi-oc ahed on om he se o disk iangula ions. Mo eo e , acco ding o De ini ion
4, e ex a3mus ha e deg ee ≥5. Le a3 be an edge wi h ou side
b
O. Obse e ha
deg(a3) = 5 leads o he con ac ibili y o a , which con adic s he minimali y o G, hence
deg(a3)≥6. Besides, deg(ai)≥5 o i= 1,2 since o he wise a 4-con ac ible edge inciden
a aiappea s, which is impossible. The e o e,
b
Ocan be emo ed by applying De ini ion 23
(1) i deg(ai)≥6 o i= 1,2 and a3∈∂G o De ini ion 23 (2) o he wise. This inishes he
p oo o Theo em 39.

Co olla y 44. Le Gbe a iangula ion o a punc u ed su ace di e en om he disk such
ha Gis 4-minimal. Then Gis i educible i and only i Gcon ains nei he quasi-oc ahed on
componen no M-componen .
Theo em 38 shows ha 4- educ ions do no su ice o ge all i educible iangula ions
wi hin he class F2(4). I , simila ly as in [11] o closed su aces, we allow diagonal lips hen
we ge he ollowing heo em.
Theo em 45. I diagonal lips a e added o 4- educ ions as admissible ope a ions in he
amily F2(4) o iangula ions o any punc u ed su ace F2, hen he 4-minimal iangula ions
educe o he i educible iangula ions in F2(4).
18
P oo . The diagonal lip ope a ion is a way o ge ing id o quasi-oc ahed a and M-componen s
in 4-minimal iangula ions. Fo ins ance, i we lip he edge xa in an M-con igu a ion when
deg(a)≥5 (simila ly, lip xb when deg(b)≥5) we s ill ha e a iangula ion in F2(4) bu now
he edge ab is 4-con ac ible. No ice ha deg(x1)≥5 by de ini ion o an M-con igu a ion
and, mo eo e , ha some 4-con ac ible edge is de ec ed whene e deg(a) = 4 (deg(b) = 4,
espec i ely); see Rema k 36(1).
On he o he hand, by lipping an edge aia3o a quasi-oc ahed on componen , new 4-
con ac ible edges a e a ailable o pe o m u he 4- educ ions and disman le he o iginal
quasi-oc ahed on componen .
This way, any 4-minimal iangula ion u ns o be i educible wi hin he class F2(4).
Appendix: P oo s o Lemmas 20 and 43.
In o de o p o e Lemma 20, le G∈ F2
◦(4) be a ixed iangula ion o he punc u ed su ace
F2. Assume ha ab is a cn4c-edge in G, ha is, he e is a ace abx in Gwi h deg(x)≤4.
We s a wi h he ollowing echnical lemmas which de ec possible con ac ible edges and
4c-edges a ound ab.
Lemma 46. Le ab be a cn4c-edge o G∈ F2
◦(4) so ha deg(a)≥4,deg(b)≥4, and le x
be a e ex o deg ee 4 so ha abx de ines a ace o Gand V(link(x)) = {x1, a, b, x2}. Then,
he ollowing s a emen s hold:
1. ax2and bx1a e no edges o G.
2. Whene e ab and xdo no in e sec ∂G simul aneously, ax and bx a e con ac ible edges
o G.
3. Whene e xx1x2is no a c i ical 3-cycle, bo h xx1and xx2a e con ac ible edges o G.
4. I xis an inne e ex o Gand he wo e ices {a, x2}({b, x1}, espec i ely) ha e
deg ee ≥5, hen he edges x wi h ∈ {b, x1}({a, x2}, espec i ely), a e 4-con ac ible.
P oo . Suppose ax2(o bx1) is an edge o G, since deg(b)≥4, he 3-cycle ax2ba (ax1ba) does
no de ine a ace o G, and hence ab lies in a c i ical 3-cycle, con adic ing he hypo hesis.
As a consequence, i ab and xdo no in e sec ∂G simul aneously, hen he edge ax is
con ac ible. O he wise, a c i ical 3-cycle con ains ax, namely ax a wi h ∈ {b, x1, x2}, bu
i is easily deduced ha =x2is he only possibili y, eaching a con adic ion. A simila
a gumen wo ks o p o ing he con ac ibili y o bx. Simila ly, xx1and xx2a e con ac ible
whene e xx1x2is no a c i ical 3-cycle.
Lemma 47. I deg(x) = 3 hen he e exis s a iode de ec ing edge, a lag o a 4c-edge
mee ing link(x).
19
P oo . Obse e ha i deg(x) = 3, hen x∈∂G,link(x) = x1ab and ao bis an inne e ex,
hence deg(a)≥4 o deg(b)≥4. Le us conside a o be he inne e ex, whence x1, b ∈∂G.
Assume deg(a) = 4. Then a lag cen e ed a aappea s whene e deg(x1) = 3 o deg(b) =
3. In case deg(x1) = 4 o deg(b) = 4, he edge xa is a iode de ec ing. This edge u ns o
be a 4c-edge when deg(x1), deg(b)≥5.
On he o he hand, i deg(a)≥5,by Lemma 46 he edge o e ices x1and bdoes no
exis .
In o de o simpli y he no a ion, le V(link(x)) = {x1, a, b, x2}be he e ex se o
he link o he e ex x ixed in Lemma 46. Then he deg ee o e ices de ines a map
δ:V(link(x)) → {n∈N;n≥3}by δ( ) = deg( ).
Hence o h, le m=min(δ)deno e he minimum o his map, and ♯Min be he
ca dinal o he se Min =δ−1(m).
P oo o Lemma 20
Since ab is a cn4c-edge in G, he e is a ace abx in Gwi h deg(x)≤4. The case deg(x) = 3
is s udied in Lemma 47. Fo deg(x) = 4, ecall ha we deno e link(x) = x1abx2x1i
link(x) = {x1a, ab, bx2, x2x1}and link(x) = x1abx2i link(x) = {x1a, ab, bx2}.(See Figu e
2).
Case 0. No ice ha i x∈∂G and ab ⊂∂G, hen i is clea ha ab is a iode de ec ing
edge.
Acco ding o Case 0, we will conside he ea e ha xand ab do no lie simul aneously
in ∂G.
Case 1: m=3. Since h ee o mo e e ices o deg ee 3 lead o he iangula ed disk, Gis
isomo phic o he wheel g aph o 4 adii, i.e. a lag, and we each s a emen 2 in he Lemma.
Nex we deal wi h he case ♯Min = 2.I Min consis s o wo adjacen e ices hen one
eadily inds a lag cen e ed a x. O he wise i wo e ices in Min a e no adjacen , he
only possibili y is ha x∈∂G. Le ∈Min and le us conside link( ) = {x, 1, 2}wi h
2∈∂G. I 1∈G−∂G and deg( 1)≥4, hen 1is a iode de ec ing edge. I 1∈∂G,
hen, by hypo hesis, deg( 1)≥4 and x is con ac ible and so a 4c-edge i deg( 1)≥5 o a
iode de ec ing edge i deg( 1) = 4.
Finally, assume Min ={ } educes o a single e ex and V(link( )) = {x, 1, 2}. We
conside he wo ollowing cases.
Case 1.1: xis independen o deg ee 4.
Since he e a e h ee e ices u∈V(link(x)) e i ying deg(u)≥5, Lemma 46 shows ha
x is a 4c-edge unless xand ab lie in he bounda y o Gsimul aneously and x1x2is an inne
edge o G(o he wise ab is a iode de ec ing edge, as poin ed ou in Case 0).
Case 1.2: xis adjacen o some e ex o deg ee 4.
1.2.1 I x∈G−∂G, hen i∈∂G o i= 1,2 and x is a con ac ible edge. Mo eo e , x
is a 4c-edge whene e deg( i)≥5 and i is a iode de ec ing o he wise.
1.2.2 I x∈∂G he e a e wo possibili ies:
20
a) ∈ {a, b}. Le us suppose =a(analogously o =b). In his case 2=a 2∈∂G
and b∈G−∂G. Now, ab is iode de ec ing edge i deg( 2)≥4 and xa is a 4c-edge i
deg( 2) = 3 (since 26=x1and deg( 2) = 3 implies deg(b)≥5).
b) ∈ {x1, x2}. I =x1(analogously o =x2) hen 2=x1 2∈∂G. In his case,
ax1is iode de ec ing edge i deg( 2)≥4 and xx1is a 4c-edge i deg( 2) = 3 (since
26=x2and deg( 2) = 3 implies deg(a)≥5).
Case 2: m ≥4. I m≥5, Lemma 46.(4) and he assump ion a e Case 0 yield ha a
4c-edge inciden in xmus appea . The same si ua ion occu s when m= 4 and ♯Min = 1.
Thus Case 2 educes o m= 4 and ♯Min ≥2. Le u, ∈Min wo dis inc e ices. We
will s udy he ollowing possibili ies acco ding o he posi ions o he e ex xand he edge
ab wi h espec o ∂G:
2.1 x∈∂G and aand ba e inne e ices (and hence, ab is an inne edge). Obse e
ha xi∈∂G o i= 1,2 since deg(x) = 4. Le aby be he o he ace sha ing ab wi h
abx.
I yis a bounda y e ex o else is an inne e ex o deg ee a leas 5, hen ab is a
iode de ec ing edge, by de ini ion. Le us s udy he case when yis an inne e ex o
deg ee 4.
2.1.1 Suppose ha u is an edge. Then xu is a 3-cycle and, mo eo e , by Lemma 46
u 6=x2a,x1b o he e ices u, ∈Min chosen abo e. I x1x2is an edge, an
oc ahed on cen e ed a xu is ound. I x1x2is no an edge he possibili ies o he
edge u a e:
1) u =ab hen an oc ahed on cen e ed a yab appea s.
2) u =x1a(analogously u =x2b). We can assume b /∈Min (a /∈Min,
espec i ely) since, o he wise, we a e in, p e ious subcase 1). Then he edge xx1
(xx2, espec i ely) is 4-con ac ible.
2.1.2 Suppose ha u is no an edge ( ha is ux is an a c). No ice ha i ♯Min ≥3
hen a leas wo e ices in Min o m a ace wi h x, and we a e in case 2.1.1.
Thus we can assume Min ={u, }and Lemma 46 (2) yields ha ei he xb o xa
is a 4c-edge.
2.2 x, a and ba e inne e ices.
2.2.1 Suppose ha u is an edge (o , equi alen ly, xu is a ace). I , in addi ion, uand
a e inne e ices (in pa icula , i u =ab) hen an oc ahed on cen e ed a xu
is ound. Thus we can assume ha {a, b}*Min and {u, } ∩ ∂G 6=∅.
1) I u =x1a, as b /∈Min and x1∈∂G, we easily check ha xa is a iode
de ec ing edge. Simila ly, i u =x2b(x2∈∂G), xb u ns o be a iode de ec ing
edge.
2) I u =x1x2, we can assume Min ={x1, x2}(o he wise we a e in one o
he p e ious si ua ions) and hen xx1o xx2a e iode de ec ing edges. Recall
{x1, x2} ∩ ∂G 6=∅.
2.2.2 Suppose ha u is no an edge. The same a gumen s as in 2.1.2 educes his case
o 2.2.1 i ♯Min ≥3 o , o he wise, Min ={u, }and Lemma 46 (2) yields ha
ei he xb o xa is a 4c-edge.
21

2.3 xis an inne e ex and ab inne edge a dis ance 0 om ∂G ( ha is, p ecisely
ao b(bu no bo h) lies in ∂G). Le us suppose a∈∂G and ban inne e ex ( hus
xb is an inne edge). F om Lemma 46 (2), xb is a con ac ible edge. Mo eo e , i
{a, x2} ∩ Min =∅, hen xb is a 4c-edge. O he wise, {a, x2} ∩ Min 6=∅and his case
educes o p e ious cases. Indeed, i a∈Min, we a e in case 2.1. wi h aplaying he
ole o x. Simila ly, i x2∈Min,x2can play he ole o xin case 2.1 and 2.2 when
x2∈∂G and x2/∈∂G, espec i ely.
2.4 x∈∂G and ab is an inne edge a dis ance 0 om ∂G ( ha is ∂G∩{a, b} educes
o a e ex). Assume a∈∂G ( he case b∈∂G is analogous) and le aby be he o he
ace con aining ab. I ab is a iode de ec ing, we a e done; o he wise ( om de ini ion
o iode de ec ing edge) ymus be an inne e ex wi h deg(y) = 4. This case was
s udied jus in he case 2.3 by in e changing xand y.
2.5 xis an inne e ex and ab ∈∂G. F om Lemma 46(2) xa and xb a e con ac ible
edges. Since m= 4, we a e in case 2.3 when xi∈Min −∂G, o some i= 1,2, wi h
xa o xb playing he ole o ab, o i= 1,2, espec i ely. O he wise, we a e in case 2.4.
and xa (analogously xb) playing he ole o ab and he ole o xis played by uwhe e
u∈Min − {a}.

The p oo o Lemma 43 only deals wi h he occu ences o iode de ec ing edges in he
p oo o Lemma 20 as explained below. In Table 2 we summa ize he condi ions unde which
a iode de ec ing edges a e loca ed in case 2 o he p oo o Lemma 20.
m≥4, u, ∈V(link(x)),wi h u, ∈Min (see Case 2)
Case 2.1.
x∈∂G
a, b ∈G−∂G
Case 2.2.x, a, b ∈G−∂G
y∈∂G
y /∈∂G and deg(y)≥5
u edge, u ∩∂G 6=∅and a /∈Min o b /∈Min
Case 2.4.x, a ∈∂G
b∈G−∂G deg(y)≥5 o deg(y) = 4 wi h y∈∂G
Table 2: Occu ences o iode de ec ing edges in he p oo o Case 2 o Lemma 20.
P oo o Lemma 43
Le us s a by ixing a iangula ion G∈ F2(4) o he su ace F2. As F2(4) ⊆ F2
0(4), we
can ollow he pa e n o he p oo o Lemma 20 abo e. Since Gdoes no con ain lags, only
he cases in he p oo o Lemma 20 when a iode de ec ing edge appea s equi e a deepe
analysis (o he wise he same a gumen s as in he p oo o Lemma 20 wo k). Recall ha
22
iode de ec ing edges appea only in Case 0 and Case 2 o ha p oo . Occu ences in Case
2 a e desc ibed in Table 2.
Case 0 x∈∂G and ab ⊂∂G
Case 0.1 m=4 and he edge x1x2does no exis . I a /∈Min, hen he edge xx1
u ns o be a 4c-edge. O he wise, he e is an N-componen wi h pa allel edges xx1, ab.
Case 0.2 m=4 and he edge x1x2exis s (and i is necessa ily an inne edge). Obse e
ha Min ={a, b, x1, x2}yields ha Gis necessa ily he i educible iangula ion M1(K6
minus a e ex) o he M¨obius s ip gi en in [8]. This con adic s ha ab is con ac ible in
G. Simila ly, he con ac ibili y o ab implies ha he edges x2aand x1bdo no exis in G
(Lemma 46). Hence an M-componen cen e ed a abx is ound and Rema k 36 assu es ha
{x1, x2} ∩ Min =∅
Case 0.3 m=5 and he edge x1x2does no exis . Then xxiis a 4c-edge o i= 1,2.
Case 0.4 m=5 and he edge x1x2exis s. In his case, an M-con igu a ion cen e ed
a abx is ound and he p oo o he Case 0 is inished.
Case 2 m=4 See Table 2; ecall ha Min con ains a leas wo e ices u, ∈
V(link(x)).
Case 2.1 x∈∂G, a, b ∈G−∂G. This implies x1, x2∈∂G. Le aby be he o he ace
sha ing ab wi h abx.
Case 2.1.a) y∈∂G and hen ab is a iode de ec ing edge (see De ini ion 7).
1. Assume deg(y) = 4. I a∈Min, hen yx1∈∂G and deg(x1) = 3,which con adic s
he hypo hesis. (Analogously, b∈Min leads o deg(x2) = 3). Hence {u, }={x1, x2}.
No ice ha x1x2is no a bounda y edge since o he wise ∂G =x1xx2, which leads o a
con adic ion wi h y∈∂G. Mo eo e , as x1, x2∈Min, i x1x2is an inne edge he e
exis s he ace x1ax2which con adic s he con ac ibili y o ab. The e o e, he edge
x1x2does no exis in Gand hence xxiis a 4c-edge o i= 1,3 by Lemma 46.
2. Assume deg(y)≥5. I is clea ha in case ha he edge x1x2exis s, i canno be
a bounda y edge. I {u, }={a, b}, hen a quasi-oc ahed on cen e ed a abx and
emaining e ices {x1, x2, y}is ound. Suppose now a /∈Min. I x1x2is no an edge,
hen by Lemma 46 xx1is a 4c-edge. I x1x2is an edge, hen he e mus be x2/∈Min
(o he wise bx1is an edge con adic ing he hypo hesis o ab con ac ible edge) and hen
by Lemma 46 xb is a 4c-edge.
Case 2.1.b) y∈G−∂G,deg(y)≥5 ( ecall ha ab is a iode de ec ing edge).
Fi s ly, we conside {u, }={a, b}. I x1x2is no an edge, clea ly an N-con igu a ion
wi h pa allel edges ab, xx1is de ec ed. (Mo eo e , xab is he cen e o a quasi-oc ahed on
componen wi h emaining e ices {x1, x2, y}). I x1x2is a bounda y edge, hen an oc a-
hed on cen e ed a abx appea s. I x1x2is an inne edge, a quasi-oc ahed on componen
cen e ed a abx and emaining e ices {x1, x2, y}is ound.
Secondly, we conside {u, }={x1, x2}. No ice ha x1x2canno be an inne edge since
o he wise, as x1∈∂G and x1∈Min, he e should be a bounda y e ex pde ining a ace
x1x2p, and hen x2ashould be an edge con adic ing he ac ha ab is a con ac ible edge.
Mo eo e , i x1x2is a bounda y edge, hen an oc ahed on cen e ed a xx1x2is ound. I
emains o conside ha x1x2is no an edge. Then he e is an N-componen wi h pa allel
edges ab, xx1.
23
Nex , we conside {u, }={a, x2}. He e b /∈Min and hen xa is a 4c-edge by Lemma
46. (Obse e ha b∈Min co esponds o he i s subcase s udied abo e). An analogous
a gumen wo ks o {u, }={b, x1}.
Finally, we conside {u, }={a, x1}. Obse e ha in case he edge x1x2exis s, i can no
be an inne edge since x1∈Min. I x1x2is a bounda y edge, hen an oc ahed on cen e ed
a xx1ais ound. In case ha x1x2is no an edge, we ge ha xx2is a 4-con ac ible edge
by Lemma 46. An analogous a gumen wo ks o {u, }={b, x2}.
Case 2.2 x, a, b ∈G−∂G.
Acco ding o Table 2 we ha e o s udy only he case when u is an edge (hence xu is a
iangle) and u∈∂G o ∈∂G, whence x o xu is a iode de ec ing edge.
Mo eo e , i {u, } ∩ {x1, x2} 6=∅we dis inguish wo possibili ies.
a) I {u, } ∩ {x1, x2}={x1}(o x2), hen ∈ {a, b}.
I u =x1a(simila ly u =x2b), hen Lemma 46 yields ha xa is con ac ible. Now i
is no di icul o see ha his case educes o Case 2.1 abo e: xa plays he same ole as ab,
x1∈∂G plays he ole o xand bplays he ole o y.
b) I u =x1x2, hen x1x2is necessa ily a bounda y edge and xu (and x ) is a cn4c-edge.
This case educes o Case 2.4 in Lemma 20: xu plays he same ole as ab ( plays he ole o
x).
Case 2.4 x, a ∈∂G, b ∈G−∂G. I eadily ollows ha in his case x1xis a bounda y
edge (he e we use deg(x) = 4) and x1x2is an inne edge (o he wise deg(x1) = 2).
1. Fi s we analyze he case u =ab. I ax1is an edge, hen an oc ahed on cen e ed
a abx is loca ed. I ax1is no an edge and deg(x2)≥5, hen an N-componen
wi h pa allel edges ax and bx2is ound. I ax1is no an edge and deg(x2) = 4,
hen a quasi-oc ahed on componen cen e ed a abx2and emaining e ices x1, a, y is
de ec ed (obse e ha ymus be an inne e ex, o he wise a bounda y e ex o deg ee
2 appea s).
2. No ice ha when u =x1x2we ha e xi∈∂G and x2/∈∂G and x1x2is a cn4c-edge.
Then a simila a gumen as abo e wo ks wi h x1x2playing he ole o ab o ob ain
ei he an N-componen o a quasi-oc ahed on componen .
I emains o deal wi h he subcase when he se s {u, } 6={a, b}sha e exac ly one
elemen .
3. I u=aand =x1and ax1is an edge, hen an oc ahed on cen e ed a axx1is ound
and ∂G =axx1. I ax1is no an edge, as deg(b)≥5, hen ax is a 4c-edge.
4. I u=a, =x2 hen deg(x1)≥5 and deg(b)≥5 and we conclude ha by Lemma 46
xx2is a 4c-edge. Obse e ha x2is an inne e ex since xx1⊂∂G,deg(x2) = 4 and
b /∈∂G.
5. I u=b, =x1, necessa ily deg(x2), deg(a)≥5 and so xb is a 4c-edge by Lemma 46.
6. I u=b, =x2 hen x1x2yis necessa ily a ace. Mo eo e , i ax1is a bounda y edge,
hen an oc ahed on componen cen e ed a bxx2is ound and ∂G =axx1.
On he o he hand, i ax1is an inne edge hen an oc ahed on componen cen e ed a
byx2appea s whene e ax1yis a ace (so ha deg(y) = 4), i i is no a ace hen a
quasi-oc ahed on componen cen e ed a bxx2and emaining e ices x1, a, y is ound.
24
Finally, he same quasi-oc ahed on componen is loca ed in Gwhen ax1is no an edge.
This inishes he p oo o Lemma 43.

Re e ences
[1] D.W. Ba ne e, Gene a ing he iangula ions o he p ojec i e plane, J. Combin. Theo y
Se . B 33, 222-230, (1982).
[2] D.W. Ba ne e, A. L. Edelson, All 2−mani olds ha e ini ely many minimal iangula-
ions, Is ael J. Ma h. 67, 123-128, (1989).
[3] D.W. Ba ne e, A. L. Edelson, All o ien able 2−mani olds ha e ini ely many minimal
iangula ions, Is ael J. Ma h. 62, 90-98, (1988).
[4] A. Boulch, ´
E. Colin de Ve di`e e, A. Nakamo o, I educible iangula ions o su aces wi h
bounda y, G aphs Comb., 29 No. 6:1675–1688, (2013).
[5] R. Bowen, S. Fisk, Gene a ion o iangula ions o he sphe e, Ma h. Compu . 21, 250–252,
(1967).
[6] M.J. Ch´a ez, S. Law encenko, J.R. Po illo, M.T. Villa , An algo i hm ha cons uc s i -
educible iangula ions o once-punc u ed su aces ”P oceedings o he XV Spanish Mee -
ing on Compu a ional Geome y” (June 26-28, 2013, Se illa, Spain) / J.M. D´ıaz-B´a˜nez,
D. Ga ijo, A. M´a quez, and J. U u ia (Eds). - Se ille: P ensa Uni e sidad de Se illa,
2013, pp. 43-46. h p://cong eso.us.es/ecgeome y/p oceedingsECG2013.pd
[7] M.J. Ch´a ez, S. Law encenko, J.R. Po illo, M.T. Villa , An algo i hm ha cons uc s
i educible iangula ions o once-punc u ed su aces, a Xi e-p in se ice, Co nell Uni-
e si y Lib a y, Pape No. a Xi :ma h/0606690 1, 9 p., (2014).
[8] M.J. Ch´a ez, S. Law encenko, A. Quin e o, M. T. Villa , I educible iangula ions o he
M¨obius band, Bul. Acad. S ¸iin ¸e Repub. Mold. Ma ., No. 2(75), 44–50, (2014).
[9] B. Chen, J.H. Kwak, S. Law encenko, Weinbe g bounds o e nonsphe ical g aphs, Jou nal
o G aph Theo y, ol. 33, issue 4, 220-236, (2000).
[10] H.H. Glo e , J.P. Huneke, C.S. Wang, 103 G aphs ha a e i educible o he p ojec i e
plane, J. Combin. Theo y Se . B 27, 332-370, (1979).
[11] H. Komu o, A. Nakamo o, S. Negami, Diagonal lips in iangula ions on closed su aces
whi h minimum deg ee a leas 4, J. Combin. Theo y Se . B 76, 68-92, (1999).
[12] S. Law encenko, On he numbe o iangula embeddings o a labeled g aph in he p ojec-
i e plane [in Russian], Uk ainskii Geome icheskii Sbo nik, No. 32, 71-84, (1989). [English
ansla ion: S. A. Law encenko, Numbe o iangula packings o a ma ked g aph on a
p ojec i e plane, Jou nal o Ma hema ical Sciences 59, no. 2, 741-749, (1992).]
[13] S. Law encenko, The i educible iangula ions o he To us, (in Russian) Uk ain. Geom.
Sb. 30 (1987), 52-62; Engl. ansl. J. So ie Ma h. 51, 2537-2543, (1990).
25