Generating families of surface triangulations. The case of punctured surfaces with inner degree at least 4

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