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

arXiv:1507.03975v2 [math.CO] 15 Jul 2015 Generating families of surface triangulations. The case of punctured surfaces with inner degree at least 4 Mar´ıa-Jos´e Ch´avez∗Seiya Negami †Antonio Quintero ‡ Mar´ıa Trinidad Villar§ Abstract We present two versions of a method for generating all triangulations of any punctured surface in each of these two families: (1) triangulations with inner vertices of degree ≥4 and boundary vertices of degree ≥3 and (2) triangulations with all vertices of degree ≥4. The method is based on a series of reversible operations, termed reductions, which lead to a minimal set of triangulations in each family. Throughout the process the triangulations remain within the corresponding family. Moreover, for the family (1) these operations reduce to the well-known edge contractions and removals of octahedra. The main results are proved by an exhaustive analysis of all possible local configurations which admit a reduction. Keywords: punctured surface, irreducible triangulation, edge contraction, vertex splitting, removal/addition of octahedra. This work has been partially supported by PAI FQM-164; PAI FQM-189; MTM 201020445. 1 Introduction By a triangulation of a surface F2we mean a simple graph G(i.e., a graph without loops and multiple edges) embedded in F2so that each face is bounded by a 3-cycle and any two faces share at most one edge. In other words, the vertices, edges and faces of G(the corresponding sets denoted by V(G), E(G) and F(G), respectively) form a simplicial complex whose underlying space is F2. Two triangulations Gand G′of F2are equivalent if there is a homeomorphism ϕ:F2→F2with ϕ(G) = G′. In this paper surfaces are supposed to be compact and connected and possibly with boundary. Surfaces without boundary will be termed closed surfaces. Here, we distinguish between triangulations only up to equivalence. Generation from irreducible triangulations of a surface F2is a well-known procedure for obtaining all the triangulations of F2. Recall that an edge of a triangulation Gof F2 is contractible if the vertices of the edge can be identified (multiple edges are removed, if they appear) and the result is still a triangulation of F2([2]). A triangulation is said to ∗Departamento de Matem´atica Aplicada I, Universidad de Sevilla, Spain, [email protected] †Research Institute of Environment and Information Sciences, Yokohama National University, 79-2 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan, [email protected]p ‡Departamento de Geometr´ıa y Topolog´ıa Universidad de Sevilla, Spain, quin[email protected] §Departamento de Geometr´ıa y Topolog´ıa, Universidad de Sevilla, Spain, [email protected] 1 be irreducible if it has no contractible edge. Irreducible triangulations form a generating set for all triangulations of the same surface in the sense that every triangulation of the surface can be obtained from some irreducible triangulation by a sequence of vertex splittings (the inverse of the edge contraction operation); see [2]. Barnette and Edelson [2] showed that every closed surface has finitely many irreducible triangulations. More recently, Boulch, Colin de Verdi`ere, and Nakamoto [4] showed the same result for compact surfaces with a nonempty boundary. Notwithstanding, it is far from being trivial to enumerate the irreducible triangulations of a given surface. Complete lists of irreducible triangulations are available only for some low genus surfaces. See [20], [22], [23] for a comprehensive reference for the class of closed surfaces. So far, the research on irreducible triangulations of closed surfaces has produced a considerable literature. This is not the case for surfaces with boundary, for which few references can be presently found; see [4], [8]. This paper is a contribution to the study of irreducible triangulations for punctured surfaces (i.e., surfaces with a hole produced by the deletion of the interior of a disk in closed surfaces). It is well known that any irreducible triangulation Gof an arbitrary non-spherical closed surface F2has minimum degree ≥4 [20]. This is no longer true if F2has non-empty boundary. However, if a boundary vertex vhas degree 2 then vlies in exactly one face of G whose boundary edges are trivially contractible (unless Greduces to a triangle). Therefore we will deal exclusively with triangulations with minimum degree ≥3. Notice that this condition implies that no face shares more than one edge with the boundary of the surface. This way, all irreducible triangulations of a surface with boundary F2(other than the disk) are elements of the class F2 ◦(4) consisting of all triangulations of F2with minimum degree ≥3 and deg(v)≥4 for all vertices vmissing the boundary. In this paper we give a generating theorem for such triangulations in terms of internal operations in the class F2 ◦(4); that is, we show that all triangulations of a punctured surface other than the disk can be reduced to an irreducible triangulation by performing such operations (Theorem 18). The particular case of the disk is also treated (Theorem 19). Similarly, we introduce a set of internal operations in the subfamily F2(4) ⊆ F2 ◦(4) consisting of all triangulations with minimum degree ≥4. In contrast with the case of closed surfaces, for a surface with non empty boundary, the minimal triangulations obtained by the use of such operations may contain contractible edges whose contraction produce 3-valent vertices. We prove that such contractible edges are necessarily located in two particular configurations given in Definitions 4 and 34, see Theorem 38. The main results collected in this work can be regarded as extensions to punctured surfaces of the main theorems by Nakamoto and Negami for closed surfaces in [17]. 2 Notation and preliminaries If Gis a triangulation of the surface F2, let ∂G ⊂Gdenote the subgraph triangulating the boundary ∂F2. The vertices and edges of ∂G will be called boundary vertices and boundary edges of G, respectively. The vertices and edges of G−∂G will be called inner vertices and inner edges of G, respectively. Let us now recall that the link of a vertex x∈G, denoted link(x), is the set of edges in Gwhich jointly with the vertex xform a triangle in G. Let e=v1v2be an edge in G. Let us recall that the distance from eto ∂G, denoted 2 d(e, ∂G), is defined to be the minimum number of edges needed to connect eand ∂G. The resulting graph obtained by contracting ein Gis denoted by G/e. The contraction of a pair of disjoint edges in two adjacent faces in Gis named double contraction. If e=v1v2 is a contractible edge of G, then the new vertex v=v1=v2in G/e satisfies deg(v) = deg(v1) + deg(v2)−3 when eis a boundary edge of G, and deg(v) = deg(v1) + deg(v2)−4 otherwise. Here deg(v) denotes the degree of the vertex v, if deg(v) = kwe say that vis a k-valent vertex. A 3-cycle in Gis critical if it consists of three edges which do not bound a face of G. Besides, if xv1v2is a face of G, then deg(x) diminishes by one after the contraction of e. When a lower bound kfor the degree of the vertices is preserved after contractions we will use the term k-contraction. Namely, given a triangulation Gwith minimum degree ≥k, an edge eis said to be k-contractible (kc-edge for short) if the minimum degree of G/e is at least k. If an edge eis contractible but not k-contractible, we call eto be a cnkc-edge, for short. The inverse operation of the contraction of the edge e=v1v2is the splitting of v1=v2. When deg(vi)≥kfor i= 1,2, after the splitting, this will be called a k-splitting. Remark 1.Notice that the contraction of an edge e∈Gbelonging to a critical 3-cycle produces a double edge. On the other hand, if ebelongs to no critical 3-cycle and at most one of its end vertices belongs to ∂G, then eis contractible. In other words, the impediments to the contractibility of eare the two following locations of ein G: (1) ebelongs to a critical cycle of G. This is the case if elies on the boundary of a hole of length 3. (2) eis an inner edge but its two vertices belong to ∂G. Remark 2.Notice that a necessary condition for an interior edge e=v1v2to be 4-contractible is that ebelongs to faces v1v2v3and v1v2v4so that deg(vi)≥5 for i= 3,4. If eis a boundary edge lying in a face v1v2v3, the necessary condition for eto be 4-contractible is that deg(v3)≥5. The following definitions extend to surfaces with boundary the one given in [17] for closed surfaces. Definition 3. Let Gbe a triangulation of a surface F2possibly with non-empty boundary. Let v1v2v3be a cycle of Gsuch that deg(vi) = 4 for i= 1,2,3 and {a1, a2, a3}be the only three vertices such that aiis adjacent to vjand vkfor {i, j, k}={1,2,3}. The subgraph H⊂Ginduced by the vertex set {a1, a2, a3, v1, v2, v3}is said to be an octahedron component centered at v1v2v3with remaining vertices a1, a2, a3if the cycle a1a2a3exists in G(and hence in H) and one of the following conditions holds: 1. vi/∈∂G for all i= 1,2,3. 2. Only one vilies in ∂G and ∂G coincides with viajak. 3. Exactly vi, vj∈∂G and hence ∂G =vivjak. 4. vi∈∂G for all i= 1,2,3 and hence ∂G =vivjvk. An octahedron component of Gis said to be external if two edges aiaj,ajaklie in ∂G (in particular, δ(aj) = 4). Observe that this happens only under condition 1. 3 a3 a1 a2 v2 v1 v3 O ∂G v3 a1 a2 v2 v1 b O ∂G v3 a1 a2 v2 v1 a3 b O ∂G a3 a3 a1 a2 v1 v3 O v2 ∂G a3 a1 a2 v1 v3 O v2 ∂G a3 a1 a2 v1 v3 O v2 ∂G a3 a1 a2 v2 v1 v3 O Figure 1: Octahedron and quasi-octahedron components in G. Definition 4. The subgraph Hin Definition 3 will be termed a quasi-octahedron component of Gcentered at v1v2v3and remaining vertices a1, a2, a3if one of the following conditions holds. (Figure 1). 1. The cycle a1a2a3exists but does not define a face in Gand only one vertex vibelongs to ∂G but (in contrast with 2 above) ajak/∈∂G. 2. Only the edge aiajfails in closing the cycle a1a2a3in G, hence vk∈∂G and all the 3-cycles of Hare faces of G. Remark 5.Notice that the possible occurrences of the subgraph Hother than the ones considered in Definitions 3 and 4 appear when at least two edges aiajdo not exist in G(and then vk∈∂G). If no edge aiajexists in G, then H=Gis a triangulation of the disk. On the other hand, if only one edge aiajis in G, then akhas degree 2 in ∂G. Notation: Octahedron and quasi-octahedron components will be denoted Oand b O, respectively. Remark 6.Let us remark also that at most one 3-cycle of an octahedron component of G may not be a face of G. In such case, ∂G reduces to that 3-cycle. Let us note that for a quasi-octahedron component of Gthe edge aiv3is always a boundary edge of G, for i= 1,2. Notice that no quasi-octahedron component b Ocan be extended to an octahedron component. Indeed, if vi∈ b O ∩ ∂G, then the 3-cycle a1a2a3is not a face even though the edge ajakopposite to viexists (and it is necessarily an inner edge). 3 Characterizing the triangulations of inner degree at least 4. It is well known that any irreducible triangulation of a closed surface other than the sphere has minimum degree ≥4. Therefore irreducible triangulations of punctured surfaces F2 (other than the disk) must have minimum inner degree ≥4 (that is, only boundary vertices are allowed to have degree 3); that is, they are in the class F2 ◦(4) defined above. 4 In this section we give a method to construct all triangulations in F2 ◦(4) from irreducible ones by operations which keeps all triangulations within this class (Theorem 18). The special case of the disk is also considered (Theorem 19). This way we generalize Theorems 1 and 2 in [17]. The method in [17] is based on the use of 4-splitting and adding octahedra. The existence of 3-valent vertices in the boundary requires two further operations: adding flags and triode 3-splittings. Throughout this section F2will denote a surface with connected (possibly empty) boundary. Recall that G∈ F2 ◦(4) denotes an arbitrary but fixed triangulation of F2with all its inner vertices of degree ≥4. Let us start by fixing some notation. Notation: If xis a vertex of Gwith deg(x) = 4 we fix notation by calling x1, x2, a, b its neighbours and for the sake of simplicity link(x) is written link(x) = x1abx2x2x1if x /∈∂G or link(x) = x1abx2if x∈∂G. This notation will be used throughout this paper without any further comment. x A removable flag x x2 v A non removable flag (x1vis a 4c-edge) x1 b a x2 ∂G ∂G a b x1 x ab inner edge, xinner vertex ab boundary edge, xinner vertex 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 inner vertices. a, x ∈∂G, binner vertex. ab inner edge, x∈∂G ab boundary edge, x∈∂G Figure 2: Different configurations for link(x), with deg(x) = 4 and distance ≤1 from ∂G. 5 The vertices of degree 3 in ∂G play a crucial role in the family F2 ◦(4). We will give them a special name. Definition 7. Given G∈ F2 ◦(4),a boundary vertex of degree 3 is called a triode of G. A contractible edge of Gis said to be a triode detecting edge if the vertices of degree 3 produced by its contraction are triodes. Remark 8.For every face abx such that ab is a contractible boundary edge, xlies in the boundary and degh(x) = 4 it readily follows from Definition 7 that ab is a triode detecting edge. On the other hand, the contraction of any inner triode detecting edge produces at most three triodes since any contraction modifies the degree of at most three vertices. It is also readily checked that two adjacent triodes define a contractible edge in ∂G, say ab, unless Gis isomorphic to the complete graph K4(and so Gtriangulates the disk). If, in addition, ab shares a face with a 4-valent inner vertex, the contraction of any edge incident at xor in link(x) is allowed in F2 ◦(4), but ab is a cn4c−edge. To get rid of this obstacle, we define the following configuration termed flag. Recall that a vertex vis said to be independent of degree kif all neighbors of vhave degree 6=k. Definition 9. Given G∈ F2 ◦(4),let xbe an independent inner vertex of degree 4 such that link(x) = x1abx2x1verifies {x1a, ab, bx2} ⊂ ∂G,x1x2∩∂G ={x1, x2},and deg(a) = deg(b) = 3. The subgraph induced by {x, x1, x2, a, b}is called a flag centered at x. If the graph G′=G− {a, b, x}remains in F2 ◦(4), the flag is said to be removable (see Figure 2). Conversely, we say that Gis obtained from G′by adding a flag along a boundary edge of G′. Remark 10.Observe that any flag is removable unless deg(x1) = 4 (or deg(x2) = 4) and this is the only impediment for a flag to being removable. If a flag is non-removable then either x1vor x2vis a boundary 4c-edge. The next lemma follows immediately from definitions and it will be used in the proof of Theorem 18 below. Lemma 11. Let ab be a contractible inner edge of G∈ F2 ◦(4),let xand ybe vertices so that xis a boundary vertex with deg(x) = 4 and abx and aby define two faces of G. Then ab is a triode detecting edge whenever yis a boundary vertex of deg(y)≥4or else yis an inner vertex of degree deg(y)≥5. Next definitions introduce the family of removable octahedron components, which added to 3-contractions and 4-contractions of edges lead to a minimal class of irreducible triangulations for any punctured surface in the spirit of Nakamoto and Negami’s theorem in [17]. Recall the notation in Definition 3. Definition 12. We will say that an octahedron component Oin a triangulation G∈ F2 ◦(4) is removable in F2 ◦(4) if the graph G′=G− {v1, v2, v3}remains in F2 ◦(4). We also say that G′is obtained by removing the octahedron Ofrom G. Conversely, Gis obtained from G′ by adding an octahedron. Remark 13.If G∈ F2 ◦(4) has an octahedron component O, then no edge of Ois 4-contractible (see Remark 2). However, removing the inner set of vertices {v1, v2, v3}is equivalent to three 6 consecutive edge 3-contractions (v1a2,v2a3and v3a1, for instance). Therefore, we can regard this set of 3-contractions as a single operation within the class F2 ◦(4) except in case that O is external. From Definition 12, the following result gives us sufficient conditions for an octahedron being removable. Remark 14.An octahedron component Ois removable in G∈ F2 ◦(4) when any of the following cases holds: •All vertices a1, a2, a3, have degree ≥6. •At least one of the vertices {a1, a2, a3}lies in ∂G and its degree is equal to 5. Observe that at least one boundary vertex of degree 3 appears after the removal of O. On the other hand, if Odoes not hit ∂G and deg(ai) = 5 for some i∈ {1,2,3}, then O is not removable but the edge aivis 4c-edge where vis the only neighbour of aioutside O. Observe that external octahedra are configurations with many vertices and edges which are not relevant from the topological point of view. We let them to be deleted according to the following definition. Definition 15. Let Obe an external octahedron component in a triangulation G∈ F2 ◦(4). If the graph G′=G− {aj, vi, i = 1,2,3}remains in F2 ◦(4), Ois said to be redundant (see Figure 3). Conversely, we say that Gis obtained from G′by adding an octahedron along a boundary edge of G′. Removable octahedron v1 v2 v3 Non-redundant octahedron Redundant octahedron a1 v a2 Figure 3: Different types of octahedra in triangulations of the M¨obius strip. Here the surface is represented by a rectangular unfolding with the opposite vertical sides identified in the usual way. Notice that after deleting any redundant octahedron component, the new triangulation; that is G′=G− {aj, vi, i = 1,2,3}, remains in F2 ◦(4). Alternatively one can regard the deletion of a redundant octahedron component Oas the composite of the folding of Ointo a face (as in Definition 22 below) and the removal of the folded octahedron component according Definition 12 Remark 16.Any addition of an octahedron in Definitions 12 and 15 is equivalent to apply three consecutive splittings in an appropriate set of vertices. Thus, if Gis a triangulation of any surface F2containing an octahedron component O, then Gis reducible. It suffices to check that the interior edges vivjand aivjof Oin Figure 1 are contractible. 7 Notice that by contracting the three edges vivjof the triangulation on the right-hand side of Figure 3, we obtain another triangulation of the M¨obius strip, depicted with thin lines. Remark 17.An external octahedron Ois not redundant whenever deg(aj) = 5 for some j∈ {1,2,3}and this is the only impediment to being redundant. This provides a triangle vajak with a boundary 4c-edge vaj(see Figure 3). After contracting vajtwo possible situations appear: (i) Obecomes redundant. (ii) Oremains non-redundant. In case (ii), a new boundary 4c-edge v′ajappears whose contraction leads us again to case (i) or (ii). By iterating this procedure, Oreaches situation (i) in finitely many steps. Otherwise Greduces to O, and so Gtriangulates the disk. Next we present the main theorems of this section. Theorem 18. Every triangulation G∈ F2 ◦(4),of a punctured surface F2, except the disk, can be obtained from an irreducible triangulation of F2by a sequence of 3-splitting triodes, additions of flags, 4-splittings and additions of octahedra. Theorem 19. Every triangulation G∈ F2 ◦(4) of the disk can be obtained from a flag or an octahedron component by a sequence of 3-splitting triodes, additions of flags, 4-splittings and additions of octahedra. The proofs of these results are consequence of the following technical lemma which deals with the possible configurations near the boundary. This is the crucial difference with the ordinary case of closed surfaces studied in [17]. Lemma 20. Assume that ab is a cn4c-edge in G, that is, there is a face abx in Gwith deg(x)≤4. 1. Let G∈ F2 ◦(4) be a triangulation of a punctured surface different from the disk. If d(ab, ∂G)≤1, then either a 4c-edge or a subgraph H⊆Gin the family A={octahedron component,triode detecting edge,flag} can be found at distance at most 1 from ab. 2. If Gtriangulates the disk, then the subgraph G′may reduce to a flag or an octahedron. For the sake of simplicity we will give the proof of Lemma 20 in the final appendix. Remark 21.It is straightforwardly checked that an octahedron component Ois not contractible to a flag within the family F2 ◦(4); that is, any contraction of any inner edge in O produces an inner 3-valent vertex. Hence, flags and octahedra are needed for generating all triangulations with minimum inner degree 4. Proof of Theorems 18 and 19. We will show that for any reducible triangulation G∈ F2 ◦(4),every cn4c-edge which is not a triode detecting edge lies in a removable octahedron or in a removable flag. This way, an irreducible triangulation G′can be obtained recursively 8 from G. Conversely, Gis constructed from G′by a sequence of 3-splitting triodes, additions of flags, 4-splittings and additions of octahedra. Assume Gcontains neither 4c-edges nor triode detecting edge. Since Gis reducible, let ab be a cn4c-edge in Gand therefore, a vertex xwith deg(x)≤4 defines a face abx of Gand x1abx2⊆link(x) (the edge x1x2may exist or not). Let us remark that the case d(ab, ∂G)≥2 admits the same kind of arguments given in Lemma 1 of [17] for closed surfaces to find either an octahedron or a 4c-edge. Hence, we focuss on the case d(ab, ∂G)≤1. In that case Lemma 20 leads us to one of the following cases: (a) There exists a flag Xsuch that d(ab, X)≤1, therefore Xis removable (otherwise a 4c-edge exists according to Remark 10). (b) There exists an octahedron component Osuch that d(ab, O)≤1, thus Ois removable or redundant in F2 ◦(4) (see Remarks 14 and 17). This finishes the proof.  4 On reductions of triangulations of degree at least 4. Henceforth, unless otherwise is stated, by F2we mean any punctured surface. Recall that F2(4) denotes the set of triangulations of the surface F2with all its vertices of degree ≥4. In this section we give a series of reductions involving exclusively triangulations in F2(4). The two operations introduced by Nakamoto and Negami in [17] are among such reductions and they are the only ones which are defined in absence of boundary. In particular, the triangulations of closed surfaces which are minimal for such reductions coincides with the irreducible triangulations in [17]. In sharp contrast with the class of closed surfaces, for a surface with non empty boundary, the minimal triangulations obtained by such reductions may contain contractible edges whose contraction produce 3-valent vertices. For this case, we prove in Theorem 38 that those possible contractible edges are located in two particular configurations given in Definitions 23 and 34 below. Notice that Definitions 12 and 15 restrict to the family F2(4) in the obvious way so that removable and redundant octahedra as well as removing and addition of such configurations are defined in F2(4). Besides these operations, we introduce new ones in Definitions 22, 23, 25 and 28 below. Definition 22. Let G∈ F2(4) be a triangulation of the surface F2. Let Obe an external octahedron of Gso that deg(a3) = 4 and deg(ai) = 6 for i= 1 or 2. Let vbe a vertex of G such that a1a2vis a face of G. By folding the octahedron Oonto the face a1a2vwe mean the removal of Ofollowed by the addition of an octahedron to the face a1a2v(Figure 4). The inverse operation is called unfolding an octahedron with respect to the boundary of G. Definition 23. Let G∈ F2(4) be a triangulation of F2. A quasi-octahedron component of G, b O, is said to be removable in F2(4) (or 4-removable, for short) if one of the following conditions holds: 1. The graph G′=G− {v1, v2, v3}yields a triangulation of 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 t T2 qq q Figure 14: A triangulation of the punctured double torus with precisely one M-component centered at abx and one non-removable quasi-octahedron. Here ∂G =x1xx2qbaptx1. The construction is done in a similar way as in Figure 13. We are now ready to establish and prove the main result of this section. Namely, Theorem 38. A triangulation G∈ F2(4) of the surface F2, different from the disk, is 4minimal if and only if each contractible edge (if any) of Gis located in either a non-removable quasi-octahedron component or an M-component. Theorem 39. The only 4-minimal triangulation of the disk is the octahedron. In order to prove Theorems 38 and 39 we will need the following technical lemmas. Lemma 40. Let G∈ F2(4) be a triangulation of the surface F2different from the disk. Assume in addition that Gcontains a non-4-removable octahedron component, O, then exactly one of the following statements hold: 1. There is at least one 4c-edge aitwith ai∈ O,t /∈ O and Oturns to be 4-removable after contracting ait. 2. ∂G ∩V(O)⊆ {a1, a2, a3}and this intersection contains at least two vertices ai, aj. Proof. Since Ois non-removable, Ohas an external vertex, say a1, such that deg(a1) = 5. Let us suppose that Odoes not intersect the boundary, then a1/∈∂G,deg(a2), deg(a3)≥6. Hence there is an edge a1tin G−E(O) existing the two faces ta1a2and ta1a3in G. This way, a1tis a 4c-edge. After contracting it, deg(a1) increases and the octahedron turns to be 4-removable. Moreover, if the intersection V(O)∩∂G reduces to a single vertex, let us suppose that this intersection is precisely the vertex a2. Since no edge aiajlie in ∂G then deg(a2)≥6 holds and since Ois non-removable, deg(ai) = 5 for i= 1 or i= 3. Let us suppose deg(a1) = 5 and let tbe the boundary vertex adjacent to a2and a1. Therefore ta1a2and ta1a3are faces of G, and since a1is not a boundary vertex, it readily follows that a1tis a 4c-edge of G. Again, after contracting it, the octahedron become 4-removable. Therefore, ∂G ∩V(O) contains at least two vertices ai, aj. In the following lemma we will use the operations 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 t t t Figure 15: Observe that δ(a) = 5, δ(b)≥6, δ(x2)≥6, δ(x1)≥6. Lemma 41. Let G∈ F2(4) be a triangulation of the surface F2, and let Obe a non-removable octahedron component of Gwith at least two vertices ai, ajin ∂G. Then 1. If E(O)∩∂G ={a1a2}and deg(a2) = 5, then, there is precisely one vertex v∈ link(a2)−V(O)and by applying an operation R5to G, the new triangulation G′belongs to F2(4). 2. If E(O)∩∂G ={a2a3, a1a3}and δ(a1) = 6 or δ(a2) = 6, then by applying an operation R3to G, the new triangulation G′belongs to F2(4). 3. If E(O)∩∂G =∅, then there exists precisely one vertex ajsuch that deg(aj) = 5 and there is a 4c-edge incident with aj. Proof. It is straightforwardly deduced from the definitions involved in the statements and Lemma 40 (2). Observe that V(O)∩∂G ={a1, a2, a3}implies that Ois 4-removable. As a consequence of Lemmas 40 and 41 we get Corollary 42. Any octahedron component of a triangulation in F2(4) of the surface Fcan be deleted by one of the reductions R1,R2,R3or R5of Table 1. The following is the corresponding analogue of Lemma 20 for the class F2(4). Lemma 43. Let G∈ F2(4) be a triangulation of the surface F2. If ab is a cn4c-edge in G so that d(ab, ∂G)≤1, then one of the following configurations can be found at distance at most 1 from ab: 17 1. A 4c-edge 2. A subgraph in the family B={octahedron component,quasi-octahedron component, N−component} 3. An M-component centered at abx. The proof of Lemma 43 is a specialization of the proof of Lemma 20 and it will be postponed to the final appendix. Proof of Theorems 38 and 39: Let ab a contractible edge in G. As Gis 4-minimal, ab is a cn4c-edge. Moreover, if d(ab, ∂G)) ≥2 then the same arguments given in Lemma 1 of [17] for closed surfaces allows us to find a 4c-edge or an octahedron component at distance ≤1 from ab. This contradicts the 4-minimality of G. Thus, necessarily, d(ab, ∂G)≤1 and Lemma 43, Corollary 42 and, again, the 4-minimality of Gyield that ab lies in a non-removable quasi-octahedron component or an M-component. Conversely, if the contractible edge ab belongs to a non-removable quasi-octahedron component b Othen it is not a 4c-edge since b Odoes not contain such edges by Remark 13. Moreover, b Ocannot be extended to an octahedron in Gby Remark 5. Finally, no N-component contained in b Ocan be reduced by Remark 29. Hence, no reduction Rican be applied to remove ab. On the other hand, if ab belongs to an M-component M ⊂ G, we know by Proposition 37 that Mis stable under reductions Ri(i= 1,...,6). This finishes the proof of Theorem 38. Let us consider the case of the triangulated disk. From Remark 36 no M-component may appear in a triangulation of the disk. Besides, a quasi-octahedron component b Owill be always removable according to Definition 23. In fact, it is clear that the degree ≥4 condition expels the quasi-octahedron from the set of disk triangulations. Moreover, according to Definition 4, vertex a3must have degree ≥5. Let a3tbe an edge with toutside b O. Observe that deg(a3) = 5 leads to the contractibility of at, which contradicts the minimality of G, hence deg(a3)≥6. Besides, deg(ai)≥5 for i= 1,2 since otherwise a 4-contractible edge incident at aiappears, which is impossible. Therefore, b Ocan be removed by applying Definition 23 (1) if deg(ai)≥6 for i= 1,2 and a3∈∂G or Definition 23 (2) otherwise. This finishes the proof of Theorem 39.  Corollary 44. Let Gbe a triangulation of a punctured surface different from the disk such that Gis 4-minimal. Then Gis irreducible if and only if Gcontains neither quasi-octahedron component nor M-component. Theorem 38 shows that 4-reductions do not suffice to get all irreducible triangulations within the class F2(4). If, similarly as in [11] for closed surfaces, we allow diagonal flips then we get the following theorem. Theorem 45. If diagonal flips are added to 4-reductions as admissible operations in the family F2(4) of triangulations of any punctured surface F2, then the 4-minimal triangulations reduce to the irreducible triangulations in F2(4). 18 Proof. The diagonal flip operation is a way of getting rid of quasi-octahedra and M-components in 4-minimal triangulations. For instance, if we flip the edge xa in an M-configuration when deg(a)≥5 (similarly, flip xb when deg(b)≥5) we still have a triangulation in F2(4) but now the edge ab is 4-contractible. Notice that deg(x1)≥5 by definition of an M-configuration and, moreover, that some 4-contractible edge is detected whenever deg(a) = 4 (deg(b) = 4, respectively); see Remark 36(1). On the other hand, by flipping an edge aia3of a quasi-octahedron component, new 4contractible edges are available to perform further 4-reductions and dismantle the original quasi-octahedron component. This way, any 4-minimal triangulation turns to be irreducible within the class F2(4). Appendix: Proofs of Lemmas 20 and 43. In order to prove Lemma 20, let G∈ F2 ◦(4) be a fixed triangulation of the punctured surface F2. Assume that ab is a cn4c-edge in G, that is, there is a face abx in Gwith deg(x)≤4. We start with the following technical lemmas which detect possible contractible edges and 4c-edges around ab. Lemma 46. Let ab be a cn4c-edge of G∈ F2 ◦(4) so that deg(a)≥4,deg(b)≥4, and let x be a vertex of degree 4 so that abx defines a face of Gand V(link(x)) = {x1, a, b, x2}. Then, the following statements hold: 1. ax2and bx1are not edges of G. 2. Whenever ab and xdo not intersect ∂G simultaneously, ax and bx are contractible edges of G. 3. Whenever xx1x2is not a critical 3-cycle, both xx1and xx2are contractible edges of G. 4. If xis an inner vertex of Gand the two vertices {a, x2}({b, x1}, respectively) have degree ≥5, then the edges xv with v∈ {b, x1}({a, x2}, respectively), are 4-contractible. Proof. Suppose ax2(or bx1) is an edge of G, since deg(b)≥4, the 3-cycle ax2ba (ax1ba) does not define a face of G, and hence ab lies in a critical 3-cycle, contradicting the hypothesis. As a consequence, if ab and xdo not intersect ∂G simultaneously, then the edge ax is contractible. Otherwise, a critical 3-cycle contains ax, namely axta with t∈ {b, x1, x2}, but it is easily deduced that t=x2is the only possibility, reaching a contradiction. A similar argument works for proving the contractibility of bx. Similarly, xx1and xx2are contractible whenever xx1x2is not a critical 3-cycle. Lemma 47. If deg(x) = 3 then there exists a triode detecting edge, a flag or a 4c-edge meeting link(x). 19 Proof. Observe that if deg(x) = 3, then x∈∂G,link(x) = x1ab and aor bis an inner vertex, hence deg(a)≥4 or deg(b)≥4. Let us consider ato be the inner vertex, whence x1, b ∈∂G. Assume deg(a) = 4. Then a flag centered at aappears whenever deg(x1) = 3 or deg(b) = 3. In case deg(x1) = 4 or deg(b) = 4, the edge xa is a triode detecting. This edge turns to be a 4c-edge when deg(x1), deg(b)≥5. On the other hand, if deg(a)≥5,by Lemma 46 the edge of vertices x1and bdoes not exist. In order to simplify the notation, let V(link(x)) = {x1, a, b, x2}be the vertex set of the link of the vertex xfixed in Lemma 46. Then the degree of vertices defines a map δ:V(link(x)) → {n∈N;n≥3}by δ(v) = deg(v). Henceforth, let m=min(δ)denote the minimum of this map, and ♯Min be the cardinal of the set Min =δ−1(m). Proof of Lemma 20 Since ab is a cn4c-edge in G, there is a face abx in Gwith deg(x)≤4. The case deg(x) = 3 is studied in Lemma 47. For deg(x) = 4, recall that we denote link(x) = x1abx2x1if link(x) = {x1a, ab, bx2, x2x1}and link(x) = x1abx2if link(x) = {x1a, ab, bx2}.(See Figure 2). Case 0. Notice that if x∈∂G and ab ⊂∂G, then it is clear that ab is a triode detecting edge. According to Case 0, we will consider hereafter that xand ab do not lie simultaneously in ∂G. Case 1: m=3. Since three or more vertices of degree 3 lead to the triangulated disk, Gis isomorphic to the wheel graph of 4 radii, i.e. a flag, and we reach statement 2 in the Lemma. Next we deal with the case ♯Min = 2.If Min consists of two adjacent vertices then one readily finds a flag centered at x. Otherwise if two vertices in Min are not adjacent, the only possibility is that x∈∂G. Let v∈Min and let us consider link(v) = {x, t1, t2}with vt2∈∂G. If t1∈G−∂G and deg(t1)≥4, then vt1is a triode detecting edge. If t1∈∂G, then, by hypothesis, deg(t1)≥4 and xv is contractible and so a 4c-edge if deg(t1)≥5 or a triode detecting edge if deg(t1) = 4. Finally, assume Min ={v}reduces to a single vertex and V(link(v)) = {x, t1, t2}. We consider the two following cases. Case 1.1: xis independent of degree 4. Since there are three vertices u∈V(link(x)) verifying deg(u)≥5, Lemma 46 shows that xv is a 4c-edge unless xand ab lie in the boundary of Gsimultaneously and x1x2is an inner edge of G(otherwise ab is a triode detecting edge, as pointed out in Case 0). Case 1.2: xis adjacent to some vertex of degree 4. 1.2.1 If x∈G−∂G, then vti∈∂G for i= 1,2 and xv is a contractible edge. Moreover, xv is a 4c-edge whenever deg(ti)≥5 and it is a triode detecting otherwise. 1.2.2 If x∈∂G there are two possibilities: 20 a) v∈ {a, b}. Let us suppose v=a(analogously for v=b). In this case vt2=at2∈∂G and b∈G−∂G. Now, ab is triode detecting edge if deg(t2)≥4 and xa is a 4c-edge if deg(t2) = 3 (since t26=x1and deg(t2) = 3 implies deg(b)≥5). b) v∈ {x1, x2}. If v=x1(analogously for v=x2) then vt2=x1t2∈∂G. In this case, ax1is triode detecting edge if deg(t2)≥4 and xx1is a 4c-edge if deg(t2) = 3 (since t26=x2and deg(t2) = 3 implies deg(a)≥5). Case 2: m ≥4. If m≥5, Lemma 46.(4) and the assumption after Case 0 yield that a 4c-edge incident in xmust appear. The same situation occurs when m= 4 and ♯Min = 1. Thus Case 2 reduces to m= 4 and ♯Min ≥2. Let u, v ∈Min two distinct vertices. We will study the following possibilities according to the positions of the vertex xand the edge ab with respect to ∂G: 2.1 x∈∂G and aand bare inner vertices (and hence, ab is an inner edge). Observe that xi∈∂G for i= 1,2 since deg(x) = 4. Let aby be the other face sharing ab with abx. If yis a boundary vertex or else is an inner vertex of degree at least 5, then ab is a triode detecting edge, by definition. Let us study the case when yis an inner vertex of degree 4. 2.1.1 Suppose that uv is an edge. Then xuv is a 3-cycle and, moreover, by Lemma 46 uv 6=x2a,x1bfor the vertices u, v ∈Min chosen above. If x1x2is an edge, an octahedron centered at xuv is found. If x1x2is not an edge the possibilities of the edge uv are: 1) uv =ab then an octahedron centered at yab appears. 2) uv =x1a(analogously uv =x2b). We can assume b /∈Min (a /∈Min, respectively) since, otherwise, we are in, previous subcase 1). Then the edge xx1 (xx2, respectively) is 4-contractible. 2.1.2 Suppose that uv is not an edge (that is uxv is an arc). Notice that if ♯Min ≥3 then at least two vertices in Min form a face with x, and we are in case 2.1.1. Thus we can assume Min ={u, v}and Lemma 46 (2) yields that either xb or xa is a 4c-edge. 2.2 x, a and bare inner vertices. 2.2.1 Suppose that uv is an edge (or, equivalently, xuv is a face). If, in addition, uand vare inner vertices (in particular, if uv =ab) then an octahedron centered at xuv is found. Thus we can assume that {a, b}*Min and {u, v} ∩ ∂G 6=∅. 1) If uv =x1a, as b /∈Min and x1∈∂G, we easily check that xa is a triode detecting edge. Similarly, if uv =x2b(x2∈∂G), xb turns to be a triode detecting edge. 2) If uv =x1x2, we can assume Min ={x1, x2}(otherwise we are in one of the previous situations) and then xx1or xx2are triode detecting edges. Recall {x1, x2} ∩ ∂G 6=∅. 2.2.2 Suppose that uv is not an edge. The same arguments as in 2.1.2 reduces this case to 2.2.1 if ♯Min ≥3 or, otherwise, Min ={u, v}and Lemma 46 (2) yields that either xb or xa is a 4c-edge. 21 2.3 xis an inner vertex and ab inner edge at distance 0 from ∂G (that is, precisely aor b(but not both) lies in ∂G). Let us suppose a∈∂G and ban inner vertex (thus xb is an inner edge). From Lemma 46 (2), xb is a contractible edge. Moreover, if {a, x2} ∩ Min =∅, then xb is a 4c-edge. Otherwise, {a, x2} ∩ Min 6=∅and this case reduces to previous cases. Indeed, if a∈Min, we are in case 2.1. with aplaying the role of x. Similarly, if x2∈Min,x2can play the role of xin case 2.1 and 2.2 when x2∈∂G and x2/∈∂G, respectively. 2.4 x∈∂G and ab is an inner edge at distance 0 from ∂G (that is ∂G∩{a, b}reduces to a vertex). Assume a∈∂G (the case b∈∂G is analogous) and let aby be the other face containing ab. If ab is a triode detecting, we are done; otherwise (from definition of triode detecting edge) ymust be an inner vertex with deg(y) = 4. This case was studied just in the case 2.3 by interchanging xand y. 2.5 xis an inner vertex and ab ∈∂G. From Lemma 46(2) xa and xb are contractible edges. Since m= 4, we are in case 2.3 when xi∈Min −∂G, for some i= 1,2, with xa or xb playing the role of ab, for i= 1,2, respectively. Otherwise, we are in case 2.4. and xa (analogously xb) playing the role of ab and the role of xis played by uwhere u∈Min − {a}.  The proof of Lemma 43 only deals with the occurrences of triode detecting edges in the proof of Lemma 20 as explained below. In Table 2 we summarize the conditions under which a triode detecting edges are located in case 2 of the proof of Lemma 20. m≥4, u, v ∈V(link(x)),with u, v ∈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 uv edge, uv ∩∂G 6=∅and a /∈Min or b /∈Min Case 2.4.x, a ∈∂G b∈G−∂G deg(y)≥5 or deg(y) = 4 with y∈∂G Table 2: Occurrences of triode detecting edges in the proof of Case 2 of Lemma 20. Proof of Lemma 43 Let us start by fixing a triangulation G∈ F2(4) of the surface F2. As F2(4) ⊆ F2 0(4), we can follow the pattern of the proof of Lemma 20 above. Since Gdoes not contain flags, only the cases in the proof of Lemma 20 when a triode detecting edge appears require a deeper analysis (otherwise the same arguments as in the proof of Lemma 20 work). Recall that 22 triode detecting edges appear only in Case 0 and Case 2 of that proof. Occurrences in Case 2 are described in Table 2. Case 0 x∈∂G and ab ⊂∂G Case 0.1 m=4 and the edge x1x2does not exist. If a /∈Min, then the edge xx1 turns to be a 4c-edge. Otherwise, there is an N-component with parallel edges xx1, ab. Case 0.2 m=4 and the edge x1x2exists (and it is necessarily an inner edge). Observe that Min ={a, b, x1, x2}yields that Gis necessarily the irreducible triangulation M1(K6 minus a vertex) of the M¨obius strip given in [8]. This contradicts that ab is contractible in G. Similarly, the contractibility of ab implies that the edges x2aand x1bdo not exist in G (Lemma 46). Hence an M-component centered at abx is found and Remark 36 assures that {x1, x2} ∩ Min =∅ Case 0.3 m=5 and the edge x1x2does not exist. Then xxiis a 4c-edge for i= 1,2. Case 0.4 m=5 and the edge x1x2exists. In this case, an M-configuration centered at abx is found and the proof for the Case 0 is finished. Case 2 m=4 See Table 2; recall that Min contains at least two vertices u, v ∈ V(link(x)). Case 2.1 x∈∂G, a, b ∈G−∂G. This implies x1, x2∈∂G. Let aby be the other face sharing ab with abx. Case 2.1.a) y∈∂G and then ab is a triode detecting edge (see Definition 7). 1. Assume deg(y) = 4. If a∈Min, then yx1∈∂G and deg(x1) = 3,which contradicts the hypothesis. (Analogously, b∈Min leads to deg(x2) = 3). Hence {u, v}={x1, x2}. Notice that x1x2is not a boundary edge since otherwise ∂G =x1xx2, which leads to a contradiction with y∈∂G. Moreover, as x1, x2∈Min, if x1x2is an inner edge there exists the face x1ax2which contradicts the contractibility of ab. Therefore, the edge x1x2does not exist in Gand hence xxiis a 4c-edge for i= 1,3 by Lemma 46. 2. Assume deg(y)≥5. It is clear that in case that the edge x1x2exists, it cannot be a boundary edge. If {u, v}={a, b}, then a quasi-octahedron centered at abx and remaining vertices {x1, x2, y}is found. Suppose now a /∈Min. If x1x2is not an edge, then by Lemma 46 xx1is a 4c-edge. If x1x2is an edge, then there must be x2/∈Min (otherwise bx1is an edge contradicting the hypothesis of ab contractible edge) and then by Lemma 46 xb is a 4c-edge. Case 2.1.b) y∈G−∂G,deg(y)≥5 (recall that ab is a triode detecting edge). Firstly, we consider {u, v}={a, b}. If x1x2is not an edge, clearly an N-configuration with parallel edges ab, xx1is detected. (Moreover, xab is the center of a quasi-octahedron component with remaining vertices {x1, x2, y}). If x1x2is a boundary edge, then an octahedron centered at abx appears. If x1x2is an inner edge, a quasi-octahedron component centered at abx and remaining vertices {x1, x2, y}is found. Secondly, we consider {u, v}={x1, x2}. Notice that x1x2cannot be an inner edge since otherwise, as x1∈∂G and x1∈Min, there should be a boundary vertex pdefining a face x1x2p, and then x2ashould be an edge contradicting the fact that ab is a contractible edge. Moreover, if x1x2is a boundary edge, then an octahedron centered at xx1x2is found. It remains to consider that x1x2is not an edge. Then there is an N-component with parallel edges ab, xx1. 23 Next, we consider {u, v}={a, x2}. Here b /∈Min and then xa is a 4c-edge by Lemma 46. (Observe that b∈Min corresponds to the first subcase studied above). An analogous argument works for {u, v}={b, x1}. Finally, we consider {u, v}={a, x1}. Observe that in case the edge x1x2exists, it can not be an inner edge since x1∈Min. If x1x2is a boundary edge, then an octahedron centered at xx1ais found. In case that x1x2is not an edge, we get that xx2is a 4-contractible edge by Lemma 46. An analogous argument works for {u, v}={b, x2}. Case 2.2 x, a, b ∈G−∂G. According to Table 2 we have to study only the case when uv is an edge (hence xuv is a triangle) and u∈∂G or v∈∂G, whence xv or xu is a triode detecting edge. Moreover, if {u, v} ∩ {x1, x2} 6=∅we distinguish two possibilities. a) If {u, v} ∩ {x1, x2}={x1}(or x2), then v∈ {a, b}. If uv =x1a(similarly uv =x2b), then Lemma 46 yields that xa is contractible. Now it is not difficult to see that this case reduces to Case 2.1 above: xa plays the same role as ab, x1∈∂G plays the role of xand bplays the role of y. b) If uv =x1x2, then x1x2is necessarily a boundary edge and xu (and xv) is a cn4c-edge. This case reduces to Case 2.4 in Lemma 20: xu plays the same role as ab (vplays the role of x). Case 2.4 x, a ∈∂G, b ∈G−∂G. It readily follows that in this case x1xis a boundary edge (here we use deg(x) = 4) and x1x2is an inner edge (otherwise deg(x1) = 2). 1. First we analyze the case uv =ab. If ax1is an edge, then an octahedron centered at abx is located. If ax1is not an edge and deg(x2)≥5, then an N-component with parallel edges ax and bx2is found. If ax1is not an edge and deg(x2) = 4, then a quasi-octahedron component centered at abx2and remaining vertices x1, a, y is detected (observe that ymust be an inner vertex, otherwise a boundary vertex of degree 2 appears). 2. Notice that when uv =x1x2we have xi∈∂G and x2/∈∂G and x1x2is a cn4c-edge. Then a similar argument as above works with x1x2playing the role of ab to obtain either an N-component or a quasi-octahedron component. It remains to deal with the subcase when the sets {u, v} 6={a, b}share exactly one element. 3. If u=aand v=x1and ax1is an edge, then an octahedron centered at axx1is found and ∂G =axx1. If ax1is not an edge, as deg(b)≥5, then ax is a 4c-edge. 4. If u=a,v=x2then deg(x1)≥5 and deg(b)≥5 and we conclude that by Lemma 46 xx2is a 4c-edge. Observe that x2is an inner vertex since xx1⊂∂G,deg(x2) = 4 and b /∈∂G. 5. If u=b,v=x1, necessarily deg(x2), deg(a)≥5 and so xb is a 4c-edge by Lemma 46. 6. If u=b,v=x2then x1x2yis necessarily a face. Moreover, if ax1is a boundary edge, then an octahedron component centered at bxx2is found and ∂G =axx1. On the other hand, if ax1is an inner edge then an octahedron component centered at byx2appears whenever ax1yis a face (so that deg(y) = 4), if it is not a face then a quasi-octahedron component centered at bxx2and remaining vertices x1, a, y is found. 24 Finally, the same quasi-octahedron component is located in Gwhen ax1is not an edge. This finishes the proof of Lemma 43.  References [1] D.W. Barnette, Generating the triangulations of the projective plane, J. Combin. Theory Ser. B 33, 222-230, (1982). [2] D.W. Barnette, A. L. Edelson, All 2−manifolds have finitely many minimal triangulations, Israel J. Math. 67, 123-128, (1989). [3] D.W. Barnette, A. L. Edelson, All orientable 2−manifolds have finitely many minimal triangulations, Israel J. Math. 62, 90-98, (1988). [4] A. Boulch, ´ E. Colin de Verdi`ere, A. Nakamoto, Irreducible triangulations of surfaces with boundary, Graphs Comb., 29 No. 6:1675–1688, (2013). [5] R. Bowen, S. Fisk, Generation of triangulations of the sphere, Math. Comput. 21, 250–252, (1967). [6] M.J. Ch´avez, S. Lawrencenko, J.R. Portillo, M.T. Villar, An algorithm that constructs irreducible triangulations of once-punctured surfaces ”Proceedings of the XV Spanish Meeting on Computational Geometry” (June 26-28, 2013, Sevilla, Spain) / J.M. D´ıaz-B´a˜nez, D. Garijo, A. M´arquez, and J. Urrutia (Eds). - Seville: Prensa Universidad de Sevilla, 2013, pp. 43-46. http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf [7] M.J. Ch´avez, S. Lawrencenko, J.R. Portillo, M.T. Villar, An algorithm that constructs irreducible triangulations of once-punctured surfaces, arXiv e-print service, Cornell University Library, Paper No. arXiv:math/0606690v1, 9 p., (2014). [8] M.J. Ch´avez, S. Lawrencenko, A. Quintero, M. T. Villar, Irreducible triangulations of the M¨obius band, Bul. Acad. St¸iint¸e Repub. Mold. Mat., No. 2(75), 44–50, (2014). [9] B. Chen, J.H. Kwak, S. Lawrencenko, Weinberg bounds over nonspherical graphs, Journal of Graph Theory, vol. 33, issue 4, 220-236, (2000). [10] H.H. Glover, J.P. Huneke, C.S. Wang, 103 Graphs that are irreducible for the projective plane, J. Combin. Theory Ser. B 27, 332-370, (1979). [11] H. Komuro, A. Nakamoto, S. Negami, Diagonal flips in triangulations on closed surfaces whith minimum degree at least 4, J. Combin. Theory Ser. B 76, 68-92, (1999). [12] S. Lawrencenko, On the number of triangular embeddings of a labeled graph in the projective plane [in Russian], Ukrainskii Geometricheskii Sbornik, No. 32, 71-84, (1989). [English translation: S. A. Lawrencenko, Number of triangular packings of a marked graph on a projective plane, Journal of Mathematical Sciences 59, no. 2, 741-749, (1992).] [13] S. Lawrencenko, The irreducible triangulations of the Torus, (in Russian) Ukrain. Geom. Sb. 30 (1987), 52-62; Engl. transl. J. Soviet Math. 51, 2537-2543, (1990). 25