Generating punctured surface triangulations with degree at least 4

DOI: 10.2478/auom-2022-0008 An. S¸t. Univ. Ovidius Constant¸a Vol. 30(1),2022,129–151 Generating punctured surface triangulations with degree at least 4 Mar´ıa-Jos´e Ch´avez and Seiya Negami and Antonio Quintero and Mar´ıa Trinidad Villar-Li˜n´an Abstract As a sequel of a previous paper by the authors, we present here a generating theorem for the family of triangulations of an arbitrary punctured surface with vertex degree ≥4. The method is based on a series of reversible operations termed reductions which lead to a minimal set of triangulations in such a way that all intermediate triangulations throughout the reduction process remain within the family. Besides contractible edges and octahedra, the reduction operations act on two new configurations near the surface boundary named quasi-octahedra and N-components. It is also observed that another configuration called M-component remains unaltered under any sequence of reduction operations. We show that one gets rid of M-components by flipping appropriate edges. 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 Gform a simplicial complex whose underlying space is F2. Two triangulations Gand G0of F2are equivalent if there is a Key Words: Punctured surface, irreducible triangulation, edge contraction, vertex splitting, removal/addition of octahedra, generating theorem. 2010 Mathematics Subject Classification: Primary 05C10; Secondary 57M20, 57N05. Received: 22.04.2021 Accepted: 25.07.2021 129 GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4130 homeomorphism ϕ:F2→F2with ϕ(G) = G0. 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. The enumeration of triangulated surfaces with and without boundary is applied to computation and physics (see [12] and the references therein). Three major methods to generate triangulations are presently available in the literature (see [22]). One of these methods is based on finding out a family of irreducible triangulations and obtaining from them all triangulations under the desired conditions by means of generating theorems. A variety of generating theorems can be found in the literature (see [15, 16, 17, 18, 20, 21] among others), these theorems provide certain sets of operations deviced to construct all triangulations in a given class Mfrom a subclass M0⊆Mby sequences of such operations. The subclass M0can be regarded a generating set for all triangulations in M. The operations which yield the whole class Mfrom M0are generally termed expansions. Most of the generating theorems also give operations, termed reductions, which act as the inverses of expansions, so that by sequences of reductions we get the ”minimal” subclass M0starting with the class M(see [2]). The classical reduction operation is a contraction of edges and its inverse a vertex splitting. Recall that an edge of a triangulation Gof F2is contractible if the vertices of the edge can be identified and the result is still a triangulation of F2. A triangulation is said to be irreducible if it has no contractible edges (see [1] and [3]). As a contribution to this research area, we state and prove here a generating theorem for punctured surfaces (i.e., surfaces obtained by deleting the interior of a disk in closed surfaces). It is well known that any irreducible triangulation of a non-spherical closed surface has minimum degree ≥4, [19]. This is no longer true for punctured surfaces; in fact, it is readily checked that all irreducible triangulations of a punctured surface (other than the disk) F2are elements of the class F2 ◦(4) consisting of all triangulations of Fwith minimum degree ≥3 on the boundary and degree≥4 for all inner vertices. Particular examples of irreducible triangulations with 3-valent boundary vertices can be found in [4] and [13]. A generating theorem for the class F2 ◦(4) is given in [6]. As a sequel, in this paper we introduce a set of six reversible internal operations in the subfamily F2(4) ⊆F2 ◦(4) consisting of all triangulations with minimum degree ≥4. The minimum degree at least 4 condition is particularly relevant in order to obtain 4-connected triangulations of surfaces. Several works concerning this property on closed surfaces can be found (see [15, 17], for instance). Moreover, the 4-connectivity of a triangulation is also closely related to the GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4131 hamiltonicity property. This fact has been shown by many papers since the seminal Whitney’s result [24] and Gr¨umbaun’s conjecture [9] appeared (see [8, 10, 23] and the references therein). The main result of this paper (Theorem 3) states that, given a punctured surface F, any triangulation of Fin F2(4) can be obtained from a 4-minimal triangulation by a sequence of operations that preserve the degree 4 condition during the whole procedure. This result can be regarded as an extension to punctured surfaces of the main theorems by Nakamoto and Negami for closed surfaces [18]. In fact, the operations termed 4-contractions and removals of octahedra in [18] coincide, respectively, with the operations R1and R2in this paper. Recently, the operation R2has been used in [20] under the name of R-reduction for even triangulations of closed surfaces. Furthermore, the other three operations in [20], called (P,T,Q)-reductions, are the composite of 4-contractions and their inverses. The configurations on which Q-reductions act are termed N-components in this paper. Notwithstanding N-components here always involve the boundary of a punctured surface. In contrast with the case of closed surfaces, the minimal triangulations of a punctured surface Fobtained by the use of such operations in F2(4) may contain contractible edges whose contraction produce 3-valent boundary vertices. We prove that such contractible edges are necessarily located in two particular configurations (see Theorem 1), that persist during the whole reduction process. In order to achieve the irreducible triangulation within F2(4), we consider diagonal flips of edges and state another generating theorem (Theorem 6). Recently, irreducible triangulations of the M¨obius band from [4] have been used in [7] to give a hint of the width of the gap between the simplicial Lusternik-Schnirelmann (L-S) category of a triangulated surface and the minimum number of critical elements of its Morse functions. The width of such a gap is far from being estimated yet. It might be expected that the present work jointly with its companion [6] enlighten the ongoing research concerning this problem. 2 New reductions/expansions for the family F2(4) With the same terminology as used in [2], in this section we introduce the reduction/expansion operations involved in the main results of the paper (Theorems 1 and 3) others than classical edge contraction and octahedron removal and its inverses, vertex splitting and octahedron addition, respectively. Throughout this paper F2will denote a surface with connected (possibly empty) boundary. If Gis a triangulation of the surface F2, let ∂G ⊂Gdenote the subgraph triangulating the boundary ∂F 2. The vertices and edges of ∂G GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4132 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. The link of a vertex x∈G, denoted link(x) = x1x2...xn, is the set of edges xixi+1 in Gwhich jointly with the vertex xform a triangle xixi+1xin Gfor 1 ≤i≤n−1. Observe that if xis an inner vertex, xn=x1. In addition, let us introduce further terminology concerning edge contraction. Henceforth, G/e will denote the contraction of the edge e=v1v2 in the graph G. Notice that 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. Besides, if xv1v2is a face of G, then deg(x) diminishes by one after the contraction of e. Here deg(v) denotes the degree of the vertex v. The vertex vis said to be k-valent if deg(v) = k. 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. The contraction of such an edge is termed a k-contraction.The corresponding vertex splitting will be called a k-splitting. In this paper by a cn4c-edge we mean a contractible edge which is not 4-contractible. Remark 1. Notice that for any interior 4c-edge e, the vertices in Gsharing a face with ehave degree ≥5. Remark 2. The two following locations of edge eare obstructions to contractibility of e. By a critical 3-cycle we mean a 3-cycle whose three edges do not bound a face of G. (1) ebelongs to a critical cycle of G. This is the case when elies on a boundary of length 3. (2) eis an inner edge but its two vertices belong to ∂G. Since F2(4) is a subfamily of F2 ◦(4) results from [6] also apply to surfaces in F2(4). In particular, we will use [6], Proposition 3.3. Recall that the distance from an edge eto ∂G, denoted d(e, ∂G), is defined to be the minimum number of edges needed to connected eand ∂G. Lemma 1. [6] Let G∈F2 ◦(4) be a triangulation of the punctured surface F2. Assume that ab is a cn4c-edge in G, and let abx be a face with deg(x)≤4. If Gis different from the disk and 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. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4133 xx x2 v x1 b a x2 ∂G∂G a b x1 Figure 1: Flags. In this lemma the following terminology from [6] is used. Definition 1. A 3c-edge eof Gis said to be a triode detecting edge if the posible vertices of degree 3 in G/e belong to the boundary. The configurations termed flags in Lemma 1 are ruled out in the family F2(4) since they contain two vertices of degree 3 on ∂G. It readily follows from Definition 1 that ab is a triode detecting edge whenever abx is a face such that ab is a contractible boundary edge, xlies in the boundary and deg(x) = 4. However triode detecting edges can appear. By focusing on this possibility we find new subgraphs involving triode detecting edges on Gthat give rise to new configurations and therefore the necessity of new reduction operations to remove then within the class F2(4). The first configuration, termed a quasi-octahedron component, is a variation of the well known notion of octahedron given in [18] and [6]. Let us start by recalling the latter. Definition 2. A graph H⊆G(possibly H∩∂G 6=∅) of vertices set {a1, a2, a3, v1, v2, v3}is said to be an octahedron component centered at the 3-cycle v1v2v3if deg(vi) = 4 in G(for 1 ≤i≤3) and the edges set of His {vivj, aiajfor 1 ≤i, j ≤3} ∪ {viajfor i6=j}. Octahedron components are denoted by O. An octahedron component of Gis said to be external if two edges aiaj, ajaklie in ∂G (in particular, deg(aj) = 4). Notice that any edge of O−∂G is a cn4c-edge. If G∈F2(4) and G0=G− {v1, v2, v3}remains in F2(4) (or equivalently deg(ai)≥6,for 1 ≤i≤3), we say that Ois 4-removable (or, alternatively that Gis the addition of Oto G0). Remark 3. Let us first suppose that Ois not 4-removable and let us consider deg(a2) = 5. If no edge of Olies in the boundary, then deg(a1), deg(a3)≥6 and there exist the two faces a1a2vand a2a3vin Gsuch that the common edge a2vis a 4c-edge and lies in G−F2(4). GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4134 The previous reasoning is similar to the case of closed surfaces although some vertices aimay lie in the ∂G (see [18]). Notice that some face v1v2v3in Gwith its three vertices of degree 4 may have some triode detecting edges and not be the center of an octahedron component. This occurs in the configuration defined as follows. Definition 3. The subgraph Hin Definition 2 will be termed a quasi-octahedron component of Gcentered at v1v2v3and remaining vertices a1, a2, a3 if precisely one vibelongs to ∈∂G and either the edge ajak(j, k 6=i) does not exist or, otherwise, the cycle a1a2a3is not a face in Gand ∂G 6=a1a2a3. Quasi-octahedron components will be denoted by b O(see Figure 3 (right)). Let us remark that the edges aia3(for i= 1,2) necessarily are inner edges. Moreover, deg(a3)≥5 since otherwise, this quasi-octahedron becomes an octahedron. If, in addition, a3∈∂G, it is clear that deg(a3)≥6. For the sake of simplicity, we henceforth assume that v3∈∂G in any quasi-octahedron component. Remark 4. Let us consider a quasi-octahedron component b O. If deg(ai) = 4, for some i= 1,2, then there exists a boundary vertex tsuch that aitis a boundary 4c-edge. If a3∈G−∂G and deg(a3) = 5, since aia3is an inner edge for i= 1,2, there must exist a vertex tdefining two faces aia3t(i= 1,2) and the edge a3tis 4-contractible. In both cases after contracting the 4c-edge ait(for i= 1,2), we observe that the quasi-octahedron remains unaltered and deg(a3)≥6 becomes after a finite number of similar edge contractions in the new triangulation. After the previous observations, without loss of generality, if no edge incident with ai, (i= 1,2,3) is 4-contractible, we may suppose that deg(ai)≥5 for i= 1,2 and deg(a3)≥6. The new reduction operations needed to deal with configurations containing triode detecting edges will be defined in the following subsections. 2.1 New reduction/expansion operations involving octahedron and quasi-octahedron components In order to ease the reading, in an external octahedron component the vertex a3will be assumed to be of degree 4. Similarly in any quasi-octahedron component the vertex v3will be assumed to be the only vertex viin ∂G. Let Obe an external octahedron component such that deg(a1) = 6 or deg(a2) = 6. Then Ois not 4-removable although it is redundant from the GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4135 topological point of view (see Figure 2(left)). To get rid of such components we introduce the following operation. By folding the octahedron Oonto the face a1a2vwe mean the removal of vertices a3, v1, v2, v3from Gfollowed by the addition of an octahedron to the face a1a2v(Figure 2). The inverse operation is called unfolding an octahedron with respect to the boundary of G. a1 v a2 a3 v3 v1 v2 a1 v a2 v3 v2v1 ∂G ∂G Figure 2: Folding the octahedron Oonto the face a1a2v. Another obstruction to reduce an octahedron component Owithin the class F2(4) arises when Ohits the boundary in exactly one edge a1a2and such that no edge aivis 4-contractible, and deg(a2) = 5. For this configurations we will introduce a further reduction operation as follows. Let vbe the only neighbour of a2outside O(Figure 3). The replacement of the boundary octahedron Oby a quasi-octahedron b Ois defined to be the removal of the edge a1a2followed by the contraction of the edge a2vin G. The inverse operation is called the replacement of the quasi-octahedron b Oby a boundary octahedron O. a1a2 a3 v v3 v1 v2 a1v3a2 v2v1 a3 ∂G ∂G Figure 3: A replacement of a boundary octahedron by a quasi-octahedron b O. The replacement of Oby b Ocan be regarded as removing the edge a1a2 and them contracting the edge a2v. Notice that the edge a1a2turns to be a 4c-edge after deleting a1a2. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4136 Definition 4. Aquasi-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 G0=G− {v1, v2, v3}yields a triangulation in F2(4). (2) If replacing the quasi-octahedron component Oby the face a1a2a3yields a triangulation in F2(4). In both cases, we will simply say that G0is obtained by removing a quasioctahedron from G. Conversely, if (1) happens, we say that Gis obtained from G0by adding a quasi-octahedron along two consecutive boundary edges of G0. In (2) we say that Gis obtained from G0by embedding a quasi-octahedron in a face of G0sharing one edge with ∂G0. Non removable quasi-octahedra Removable quasi-octahedron a3 a1 a2 v1v2 v3 v2 a1 v3 a2 v1 a3 Removable quasi-octahedra v2 a1 v3 a2 v1 a3 a2 a3 a2 a3 a2 Figure 4: Triangulations for the M¨obius strip with some quasi-octahedra components. In both cases G0is obtained from Gby a sequence of three successive edge contractions. As a consequence, if Gcontains a quasi-octahedron component b O, then Gis reducible. Indeed, the interior edges vivjand aivjof b Oare readily checked to be cn4c-edges. Let us observe other facts with regard to removing quasi-octahedra. Conditions (1) and (2) above are not mutually exclusive. Indeed, in Figure 3 (right) both ways of removing the quasi-octahedron can be carried out whenever a3is an inner vertex, the edge a1a2does not exist and deg(ai)≥6 for i= 1,2,3. Other possibilities for removing a quasi-octahedron may appear as it is illustrated in Figure 4. The removable quasi-octahedron in Figure 4 (center) verifies only condition (2), while the removable quasioctahedron in Figure 4 (right) verifies only condition (1). We can establish the following characterization of a non-removable quasioctahedron. Proposition 1. Let G∈F2(4) be a triangulation of the surface F2and b Obe a quasi-octahedron component of G. Then, b Ois not removable in F2(4) if and only if one of the following conditions holds: GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4137 (a.1) a3∈G−∂G and deg(ai)=4for some i= 1,2. (a.2) a3∈G−∂G and deg(a3)≤5. (b.1) a3∈∂G and a1a2is an inner edge of G, (or, equivalently, v3a1and v3a2 are non-contractible edges). (b.2) a3∈∂G and deg(ai) = 4 for some i= 1,2. Proof. If a3is an inner vertex, deleting the quasi-octahedron via (1) provides a triangulation of the same surface. Hence, (1) holds if and only if deg(ai)≥6 (i= 1,2,3). Otherwise, condition (2) holds if and only if a1and a2are not adjacent and deg(ai)≥5 (i= 1,2) and deg(a3)≥6. Therefore, in this case, b Ois not removable in F2(4) if and only if (a.1) or (a.2) is verified. If a3is a boundary vertex, then by Remark 4 deg(a3)≥6 holds. If a1a2is an inner edge (or, equivalently, the edges v3a1and v3a2are noncontractible), the quasi-octahedron is not removable since by removing it by condition (1) a singular boundary point occurs and removing it by condition (2) provides a double edge a1a2. Therefore, if a3∈∂G (2) holds if and only if deg(a1), deg(a2)≥5 and the edges v3a1and v3a2are contractible. Hence, in this case, b Ois not removable in F2(4) if and only if (b.1) or (b.2) is verified. 2.2 A new reduction/expansion operations involving triode detecting edges Quasi-octahedron components do not exhaust all possible appearance of triode detecting edges in triangulations in F2(4) (see Figure 5, left and center). Pursuing our goal of finding minimal triangulation in the family F2(4), we detect a new configuration in Gand define a new operation to reduce it within F2(4) to reach a minimum number of unavoidable triode detecting edges in G. Definition 5. An N-component of a triangulation G∈F2(4) of the surface F2consists of a subgraph Nof Gdetermined by two faces sharing an edge, where at least two non-incident edges are cn4c-edges and at least one of them lies in ∂G (Figure 5). An N-component N⊂Gis termed contractible if both non-incident contractible edges lie in the boundary or else some inner vertex in Nhas degree ≥5. In such configurations, the simultaneous contractions of the two nonincident contractible edges in Nyields a triangulation in F2(4). This double contraction will be called contracting an N-component. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4144 it is not a 4c-edge since b Odoes not contain such edges. Moreover, b Ocannot be extended to an octahedron in Gby Definition 3. Finally, no N-component contained in b Ocan be reduced by Remark 5. 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 2 that Mis stable under reductions Ri(i= 1,...,6). This finishes the proof of Theorem 1. Let us consider the case of the triangulated disk. From Remark 6 no M-component may appear in a triangulation of the disk. Besides, a quasioctahedron component b Owill be always removable according to Definition 4. In fact, it is clear that the degree ≥4 condition expels the quasi-octahedron from the set of disk triangulations. Moreover, according to Definition 3, 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 O can be removed by applying Definition 4 (1) if deg(ai)≥6 for i= 1,2 and a3∈∂G or Definition 4 (2) otherwise. This finishes the proof of Theorem 2.  4 Further developments According to Proposition 4, it may occur that given a triangulation Gin F2(4) all possible 4-minimal triangulations obtained from Gby applying the 4-reductions in Table 1 are reducible. To bridge this gap, it is natural to ask for new 4-reduction operations to be defined in F2(4), such that the corresponding triangulations are irreducible. Alternatively, one may look for further operations (not increasing the number of vertices and edges) to be added to the family of Ri-operations in order to reach the same goal. With regard to the latter, let us observe that any 4-minimal triangulation admits further reductions by allowing diagonal flips. Actually, diagonal flips have been already considered in relation with irreducible triangulations of closed surfaces in [11] and [19]; in fact, the Q-reduction operation described in [20] can be regarded as the composite of a diagonal flip and an edge contraction. Concerning this problem we can prove the following result, which gives a way of turning 4-minimal triangulations into irreducible. Theorem 1 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 that preserve the 4-degree condition, then we get the following theorem. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4145 Theorem 5. If diagonal flips are added to 4-reductions as admissible operations in the family F2(4) of triangulations of a given punctured surface F2, then the 4-minimal triangulations are exactly the irreducible triangulations in F2(4). 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 x1ain an M-configuration when deg(a)≥5 (similarly, flip x2bwhen 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 6(1)). On the other hand, by flipping an edge aia3of a quasi-octahedron component, new 4-contractible edges are available to perform further 4-reductions and dismantle the original quasi-octahedron component. As a consequence, we conclude with another generating theorem with the same flavour as Theorem 3. Theorem 6. Let F2be a punctured surface. Any triangulation in F2(4) can be obtained from an irreducible triangulation by a sequence of 4-expansions and diagonal flips. Appendix: Proof of Lemma 3 Let us start by fixing some notation. Besides the edge ab and the vertex x given by Lemma 3, we will denote by x1and x2the vertices adjacent to xfor which link(x) = x1abx2x1if x /∈∂G or link(x) = x1abx2if x∈∂G. Recall that a vertex vis said to be independent of degree kif all neighbours of vhave degree 6=k. Lemma 1 establishes that the edge ab is at distance at most 1 from a subgraph Hof Gwich is isomorphic to a 4c-edge or an ocathedron component or a triode detecting edge or a flag. Moreover, if Gtriangulates the disk, then Hmay reduce to a flag or an octahedron. Since we are dealing with G∈F2(4), Hcannot be a flag. Hence we can take advantage of the other cases given by Lemma 1 and focus on the situation in which His a triode detecting edge located within a quasi-octahedron, or an N-component, or an M-component at distance less than or equal to 1 from ab. After the previous observations, all remaining cases correspond to the ones depicted in Figure 7. We will next analyze these cases by following the Roman numbering in Figure 7. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4146 x ab inner edge, xinner vertex ab boundary edge, xinner vertex a a aa a a b bb bb b b xx x x x x1 x1 x1x1 x1 x1x2 x2 x2 x2 x2 x2 y y ∂G ∂G ∂G ∂G ∂G ∂G ∂G a∈∂G,xand binner vertices a, x ∈∂G, binner vertex ab inner edge, x∈∂G ab boundary edge, x∈∂G (IV.a) (VI) (III.a) (II) (I) (V) a b x x1 x2 ∂G (IV.b) a b x x1 x2 ∂G (III.b) Figure 7: Different configurations for link(x), with deg(x) = 4 and distance at most 1 from ∂G. (I) x∈∂G and ab ⊂∂G. If abx is the center of an M-component, statement 3 holds. Otherwise, x1and x2do not define an edge and xxiis a contractible edge, for i= 1,2. We distinguish two cases according to deg(a) and deg(b). If deg(a)≥5 (or deg(b)≥5), then the edge xx1turns to be a 4c-edge. Otherwise (deg(a) = 4 and deg(b) = 4), there is an N-component with parallel edges xx1, ab. Notice that xand ab do not lie simultaneously in ∂G except for Case (I). Let m≥4 denote the minimum degree of the vertices of link(x). If m≥5, then it is not difficult to check that a 4c-edge incident in x must appear. A similar situation occurs if m= 4 and only one vertex of link(x) has degree 4. Next we can deal cases (II) - (VI) under the following assumption. (A) m= 4 with at least two vertices {u, v} ⊂ V(link(x)) having degree m. (II) ab ⊆G−∂G,x∈∂G. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4147 If abx is the center of an octahedron component or a quasi-octahedron component, we are done. If xx1x2is the center of an octahedron, we are done. Otherwise we distinguish two cases according to the existence of the inner edge x1x2or not. Observe that with these conditions we get deg(a)≥5 or deg(b)≥5. If x1x2does not exist, then xxiis a 4c-edge (for i= 1 or 2) If x1x2does exist, it must be an inner edge. Since ab is contractible, we can suppose b∈G−∂G and xb contractible edge. Moreover, deg(a)≥5 since deg(a) = 4 implies the existence of the edge bx1and this contradicts the contractibility of ab. Observe that in this case deg(x2)≥5, since otherwise x2bx1must define a face of G, contradicting again the contractibility of ab. Therefore, xb is a 4c-edge and this case is finished. (III.a) ab ⊆G−∂G,x∈G−∂G,x1x2⊆∂G. If abx is the center of an octahedron component we are done. If axx1 (analogously bxx2) is the center of an octahedron component or a quasioctahedron component, we are done. Otherwise, the 4-valent vertices of link(x) can not be adjacent, except possibly x1and x2. Let us suppose deg(a) = deg(x2) = 4 (deg(b) = deg(x1) = 4 is analogous), then deg(b)≥5 and deg(x1)≥5 implies xb and xx1are 4c-edges. If deg(x1) = deg(x2) = 4, then deg(a)≥5 and deg(b)≥5, If x1x2is not contractible, it must be because of the existence of an octahedron component centered at xx1x2. Otherwise, x1x2is contractible and there exists an N-component with parallel edges xa and x1x2. (III.b) ab ⊆G−∂G,x∈G−∂G,x1x2⊆G−∂G,x1∈∂G. If abx or bx2x is the center of an octahedron component, we are done. Otherwise, by assumption (A) deg(b)≥5 and ax and xx2are 4c-edges. (IV.a) ab ⊆G−∂G,x, b ∈G−∂G,a∈∂G,ax1⊆∂G. If one of the triangles meeting xis the center of an octahedron or quasi-octahedron component, we are done. By assumption (A), there are at least two vertices of degree 4 in V(link(x)). If deg(a) = deg(x2) = 4 (analogous for deg(b) = deg(x1) = 4), then xa is 4c-edge if deg(x1)≥5 (since deg(b)≥5). If deg(x1) = 4 and ax1is contractible, then there exists an N-component with parallel edges ax1and xx2. If ax1is not contractible, then ∂G has length 3 and axx1is the center of an octahedron component. (IV.b) ab ⊆G−∂G,x, b ∈G−∂G,a∈∂G,ax1⊆G−∂G. It is not difficult to see that all edges incident in xare contractible. If xx1x2or xbx2is the center of an octahedron, we are done. Otherwise, by assumption (A), deg(x2)≥5 and xx1and xb are 4c-edges. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4148 (V) ab ⊆G−∂G,x, a ∈∂G. If xbx2is the center of an octahedron or quasi-octahedron component, we are done. If axx1is the center of a boundary octahedron component we are done. Otherwise deg(b)≥5 or deg(x2)≥5. Observe that xb is a contractible edge. We distinguish two cases: there exists inner edge ax1 or not. If ax1is an inner edge, then deg(a)≥5 since deg(a) = 4 implies the existence of the edge bx1contradicting the contractibility of ab. If deg(x2)≥5, then xb is a 4c-edge. If deg(x2) = 4, then deg(b)≥5 and it is not difficult to check that x2∈G−∂G (x2∈∂G implies x1x2 boundary edge, a contradiction). Therefore xx2is also a contractible edge. Now, notice that deg(x1)≥5 since deg(x1) = 4 implies the existence of the edge ax2contradicting the contractibility of ab. Hence, xx2 is a 4c-edge. If ax1is not an edge, then xa and xx1are contractible and one of them must be a 4c-edge since band x2can not be 4-valent vertices simultaneously. (VI) ab ⊆∂G,x∈G−∂G. If one of the triangles meeting xis the center of an octahedron or quasi-octahedron component, we are done. Otherwise, no pair of adjacent vertices are 4-valent, except possibly aand b. If deg(a) = deg(b) = 4, then an N-component with parallel edges ab,xx2 is found. If deg(a)≥5 and deg(x2)≥5, then xx1and xb are 4cedges. If deg(a)≥5 and deg(x2)=4,then deg(x1)≥5 and deg(b)≥5 (otherwise an octahaedron or quasi-octahedron appear), and xx2and xa are 4c-edges.  Acknowledgement. The authors gratefully acknowledge financial support by the Spanish Ministerio de Ciencia e Innovaci´on and Junta de Andaluc´ıa via grants MTM 2015-65397-P and PAI FQM-326; PAI FQM-164; PAI FQM-189, respectively. References [1] D.W. Barnette, A. L. Edelson, All 2−manifolds have finitely many minimal triangulations, Israel J. Math. 67 (1989), 123-128. [2] G. Brinkmann, B. D McKay Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58(2) (2007), 323-357. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4149 [3] A. Boulch, ´ E. Colin de Verdi`ere, A. Nakamoto, Irreducible triangulations of surfaces with boundary, Graphs Comb., 29 No. 6 (2013), 1675–1688. [4] 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) (2014), 44–50. [5] M.J. Ch´avez, S. Negami, A. Quintero, M. T. Villar, Generating families of surface triangulations. The case of punctured surfaces with inner degree at least 4. arXiv e-print service, Cornell University Library, http://arxiv.org/abs/1507.03975v2, (2015). [6] M.J. Ch´avez, S. Negami, A. Quintero, M. T. Villar, A generating theorem of punctured surface triangulations with inner degree at least 4. Math. Slovaca 69, No. 5 (2019), 969–978. [7] D. Fern´andez-Ternero, E. Mac´ıas-Virg´os, N. A. Scoville, J. A. Vilches Strong Discrete Morse Theory and Simplicial L-S Category: A Discrete Version of the Lusternik-Schnirelmann Theorem, Discret. Comput. Geom. 63 (2020), 607-623. [8] J. Fujisawa, A. Nakamoto, K. Ozeki, Hamiltonian cycles in bipartite toroidal graphs with a partite set of degree four vertices, J. Combin. Theory, Ser. B 103 (2013), 46-60. [9] B. Grunbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970), 1131-1201. [10] K. Kawarabayashi, K. Ozeki, 4-connected projective-planar graphs are Hamiltonian-connected, J. Combin.Theory Ser.B 112 (2015), 36-69. [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 (1999), 68-92. [12] B. Kr¨uger, K. Mecke, Genus dependence of the number of (non-)orientable surface triangulations, Phys. Rev. D 93 (2016), 085018 (6 pp). [13] S. Lawrencenko, T. Sulanke, M. T. Villar, L. V. Zgonnik, M. J. Ch´avez, J. R. Portillo. Irreducible triangulations of the once-punctured torus, Sibirskie Elektronnye Matematicheskie Izvestiya. Vol. 15 (2018), 277-304. [14] A. Malniˇc, R. Nedela, K-Minimal triangulations of surfaces, Acta Math. Univ. Comenianae 64, 1 (1995), 57-76. GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4150 [15] N. Matsumoto, A. Nakamoto, Generating 4-connected even triangulations on the sphere, Discrete Math. 338 (2015), 64-70. [16] N. Matsumoto, A. Nakamoto, T. Yamaguchi, Generating even triangulations on the torus, Discrete Mathematics 341 (2018), 2035-2048. [17] A. Nakamoto, H. Motoaki, Generating 4-connected triangulations on closed surfaces, Mem. Osaka Kyoiku Univ. Ser. III Nat. Sci. Appl. Sci. 50, no. 2 (2002), 145-153. [18] A. Nakamoto, S. Negami, Generating triangulations on closed surfaces with minimum degree at least 4, Discrete Math. 244 (2002), 345-349. [19] S. Negami, Triangulations, Handbook of Graph Theory, Second Edition. J. L. Gross, J. Yellen and P. Zhang (Ed.) Chapman and Hall/CRC Press, 876-901, 2014. [20] M. Nishina, Y. Suzuki, A generating theorem of simple even triangulations with a finitizable set of reductions, Discrete Math., 340 (2017), 2604-2613. [21] T. Sulanke, Generating irreducible triangulations of surfaces, arXiv:math/0606687v1 [math.CO], (2006). [22] T. Sulanke, F. H. Lutz, Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds, Eur. J. Comb. 30 (2009), 19651979. [23] R. Thomas, X. Yu, 4-connected projective planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994), 114-132. [24] H. Whitney, A theorem on graphs, Ann. Math. 32 (1931), 378-390. Mar´ıa-Jos´e Ch´avez, Departamento de Matem´atica Aplicada I, Universidad de Sevilla, Spain, Email: mjchav[email protected] Seiya Negami, Faculty of Environment and Information Sciences, Yokohama National University, 79-2 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan. Email: [email protected] Antonio Quintero, Departamento de Geometr´ıa y Topolog´ıa, Universidad de Sevilla, Spain, Email: quin[email protected] GENERATING PUNCTURED SURFACE TRIANGULATIONS WITH DEGREE AT LEAST 4151 Mar´ıa Trinidad Villar-Li˜n´an, Departamento de Geometr´ıa y Topolog´ıa, Universidad de Sevilla, Spain, Email: [email protected]