Vertex Spanning Planar Laman Graphs in Triangulated Surfaces

A basic object of study in Framework Rigidity is a graph \(G=(V,E)\) made of bars and joints in Euclidean space \({\mathbb {R}}^d\). Such a realization is given by specifying a map \(p:V\rightarrow {\mathbb {R}}^d\). The pair (G, p) is called a framework. It is important, for both mathematicians and engineers, to know whether the framework (G, p) is infinitesimaly rigid, namely, whether every small enough perturbation of p that preserves all the edge lengths, up to first order, is the restriction to V of some rigid motion of the entire space \(\mathbb R^d\). A graph G that admits an infinitesimally rigid framework (G, p) is called d-rigid. If G is d-rigid, a generic map \(p:V\rightarrow {\mathbb {R}}^d\) makes (G, p) infinitesimally rigid.

The following question arises: for G d-rigid, how small can a subset \(A\subseteq {\mathbb {R}}^d\) be, such that there exists an infinitesimally rigid framework (G, p) with \(p:V\rightarrow A\)? Likewise for a family F of d-rigid finite graphs: Denote by \(c_d(F)\) the minimum cardinality |A| over subsets \(A\subseteq {\mathbb {R}}^d\) satisfying that for every graph \(G\in F\) there exists \(p:V(G)\rightarrow A\) such that (G, p) is infinitesimally rigid.

Jordan and Fekete [6] showed that for the family \(F_1\) of 1-rigid graphs, namely the connected graphs, \(c_1(F_1)=2\), and for \(d\ge 2\), the family \(F_d\) of d-rigid graphs has \(c_d(F_d)=\infty \), namely no such finite A exists; see also [1]. Let us restrict to the subfamily \(F(g)\subseteq F_3\), of 1-skeleta of triangulations of the surface of genus g (orientable or not). Indeed, a fundamental result of Fogelsanger [7] asserts that for every g, every graph \(G\in F(g)\) is 3-rigid. Adiprasito and Nevo [1] showed that \(c_3(F(g))\) is finite for any fixed genus g, and asked whether there exists an absolute constant c such that \(c_3(F(g))\le c\) for all g. The same question can be asked in the plane:

Problem 1.1

Does there exist an absolute constant c such that \(c_2(F(g))\le c\) for all genus g?

Király [10] showed that \(c_2(F(g))=O(\sqrt{g})\). He also proved that for the family F(PL) of planar Laman graphs, \(c_2(F(PL))\) is finite (in fact, at most 26), answering a question of Whiteley [1, Prob. 6.4]. Thus, an answer Yes to Problem  would follow from an answer Yes to the following problem:

Problem 1.2

Does every triangulation of a surface (compact, connected, without boundary) admit a vertex spanning planar Laman graph?

This clearly holds for the 2-sphere, denoted by \(S^2\). We answer Problem 1.2 in the affirmative for the surfaces of nonnegative Euler characteristic, by proving a stronger structural-topological result:

Main Theorem 1.3

The following hold:

• Every triangulation of the projective plane \(\mathbb RP^2\) contains a vertex spanning subcomplex homeomorphic to a disc (namely to a closed 2-dimensional ball).

• Every triangulation of the torus T contains a vertex spanning subcomplex homeomorphic to a cylinder (namely to the product of a closed interval and a 1-dimensional sphere).

• Every triangulation of the Klein bottle K contains a vertex spanning, planar, 2-dimensional complex; it is either a cylinder, or a connected sum of two triangulated discs along a triangle.^{Footnote 1}

For a topological space M, denote by F(M) the family of 1-skeleta of triangulations of M.

Corollary 1.4

For \(M\in \{T,K,\mathbb RP^2,S^2\}\), \(c_2(F(M))\le 26\).

To see that Theorem 1.3 implies Corollary 1.4, note two facts: (i) all the vertex spanning subcomplexes in Theorem 1.3 have a 2-rigid graph (indeed, clearly all strongly-connected pure d-dimensional simplicial complexes have a d-rigid 1-skeleton, see e.g. [9, Lem. 6.2]), thus each of them contains a minimal 2-rigid, namely Laman, spanning subgraph; and (ii) these Laman graphs are planar—this is clear as the 2-dimensional subcomplexes containing them are themselves planar. Now apply Király’s result that \(c_2(F(PL))\le 26\) [10].

The basic idea in the proof of Theorem 1.3 is to use induction over vertex splits: first we find a suitable spanning subsurface in each irreducible triangulation of \(M\in \{T,K,\mathbb RP^2\}\), and then extend the spanning subsurface along vertex splits. One has to be careful to extend at each vertex split in such a way that the new spanning subsurface is again extendible. This is defined and explained in Sect. 3, see the Extension Theorem 3.2.

Outline. In Sect. 2 we give the necessary background on rigidity and on irreducible triangulations, in Sect. 3 we prove the Main Theorem 1.3 via proving the Extension Theorem 3.2, modulo a lemma on rearranging the vertex splits, proved in Sect. 4. We end with concluding remarks in Sect. 5.

2.1 Rigidity

Let \(G=(V,E)\) be a graph, and let \(p:V\rightarrow {\mathbb {R}}^d\) be a map. An infinitesimal motion of the framework (G, p) is a map \(a:V\rightarrow {\mathbb {R}}^d\) (think of a as an assignment of velocity vectors) such that for all edges \(vu\in V\), the following inner product vanishes:

The infinitesimal motion a is trivial if the relation above is satisfied for every pair of vertices in V; otherwise a is nontrivial. The framework (G, p) is infinitesimally rigid if all its infinitesimal motions are trivial. This definition is equivalent to the one given in the introduction. A graph G admitting such an infinitesimally rigid framework (G, p) is d-rigid. In that case the subset of maps p such that (G, p) is infinitesimally rigid is Zariski dense in the space \({\mathbb {R}}^{d|V(G)|}\) of all maps \(q:V(G)\rightarrow \mathbb R^d\). The readers may consult e.g. [5, 8, 14] for further background on rigidity.

2.2 Irreducible Triangulations

Let vu be an edge in a graph \(G=(V,E)\). Contract v to u to obtain the graph \(G'=(V-v,E')\), so \(E'=(E{\setminus }\{wv:wv\in E\})\cup \{wu:wv\in E,\,w\ne u\}\). This operation is called an edge contraction at vu. The inverse operation, that starts with \(G'\) and produces G is called a vertex split at u. Similarly one defines edge contraction for simplicial complexes: for contracting the edge uv, replace the faces of the form \(F\cup \{v\}\) in a simplicial complex \(\Delta \) (\(v\notin F\)) by \(F\cup \{u\}\) (and remove duplicates if they appear) to obtain a new simplicial complex \(\Delta '\). The inverse move, of vertex split, is described explicitly at the end of this subsection for our special case of interest, namely for triangulated surfaces and topology preserving vertex splits.

A triangulation \(\Delta \) of the surface of genus g, \(M_g\), is irreducible if each contraction of an edge of \(\Delta \) changes the topology; equivalently, the following combinatorial condition holds: each edge in \(\Delta \) belongs to an empty triangle F of \(\Delta \), namely, \(F\notin \Delta \) and its boundary complex \(\partial F\subseteq \Delta \). Barnette and Edelson showed:

Theorem 2.1

[3, 4] For all g, \(M_g\) has finitely many irreducible triangulations.

When the Euler characteristic \(\chi (M_g)\ge 0\), the irreducible triangulations were characterized (up to combinatorial isomorphism) in a series of works: the 2-sphere has a unique irreducible triangulation, namely the boundary of the tetrahedron, see e.g. Whiteley [17] for a proof that all maximal planar graphs are 3-rigid using this fact; \(\mathbb RP^2\) has two irreducible triangulations, see Barnette [2]; the torus has 21, see Lavrenchenko [12]; the Klein bottle has 29, see Lavrenchenko–Negami [11] and a correction by Sulanke [16].

We will use these characterizations in the proof of Theorem 1.3, in the next section. Note that every triangulation of \(M_g\) can be obtained from some irreducible triangulation of \(M_g\) by a sequence of vertex splits; each intermediate complex also triangulates \(M_g\).

Specifically, let \(\Delta \) be a triangulation of \(M_g\). A vertex split \(\Delta \rightarrow \Delta '\) at v is given as follows: decompose the link of v, \({{\,\textrm{lk}\,}}_v(\Delta )\), which is a cycle, into two closed intervals in the cyclic order, \([x_1,x_k]\) and \([x_k,x_1]\), where \({k\ne 1}\). Now replace the star of v in \(\Delta \) by the union of two cones over cycles \(v*(x_1,\dots ,x_k,v',x_1)\cup v'*(x_k,\dots ,x_1,v,x_k)\) (where \(v'\) is a new vertex) to obtain a triangulation \(\Delta '\) of \(M_g\).

3.1 Extendible Subsurfaces

Informally, we want the vertex split on a triangulation of \(M_g\), \(\Delta \rightarrow \Delta '\), to allow an extension \(S'\subseteq \Delta '\) of the spanning disc/cylinder/etc \(S\subseteq \Delta \); see Theorem 1.3 for the relevant topology of S. Formally, for a triangulation \(\Delta \) of the surface \(M_g\), define:

Definition 3.1

A vertex spanning subsurface (with boundary) \(S\subseteq \Delta \) is extendible if for every vertex split \(\Delta \rightarrow \Delta '\) there exists a subsurface \(S'\subseteq \Delta '\) such that either

• \(S'\) is obtained from S by a vertex split at the same vertex, denote it by v. Namely, the contraction of the edge \(vv'\) in \(S'\) results in S; or

• \(S'\) is obtained from S by adding a cone over an interval in the boundary of S. (The apex of the cone is the new vertex, in particular not in S.)

Note that such \(S'\subseteq \Delta '\) is vertex spanning and homeomorphic to S.

Extension Theorem 3.2

Let \(\Delta \) triangulate some surface \(M_g\) (compact, connected, without boundary), and let \(S\subseteq \Delta \) be a vertex spanning subsurface. Then:

1. (i)

   S is extendible in \(\Delta \) iff it contains at least one edge from every triangle in \(\Delta \).

2. (ii)

   Let \(\Delta \rightarrow \Delta '\) be a vertex split. If S is extendible then it has an extendible extension \(S'\subseteq \Delta '\).

In all the irreducible triangulations of \(\mathbb RP^2\), T, and K, except for the four so called cross-cap triangulations of the Klein bottle K (see Fig. 7), we find an extendible spanning subsurface S to start with: for \(\mathbb RP^2\) the subsurface S is a disc, and for T and K the subsurface S is a cylinder. See Fig. 1  for spanning discs in the two irreducible triangulation of \(\mathbb RP^2\), and see Fig. 2  (resp. Fig. 3) for spanning cylinders in the irreducible triangulations of the torus (resp. the non-cross-cap irreducible triangulations of Klein’s bottle).

Spanning discs, in grey, in the irreducible triangulations of the projective plane

Full size image

Spanning cylinders, in grey, in the 21 irreducible triangulations of the torus

Full size image

Spanning cylinders, in grey, in the 25 non-cross-cap irreducible triangulations of Klein’s bottle

Full size image

Proof

For a proof of the Extension Theorem 3.2, the “only if” part in (i) is easy, see Fig. 4  for an illustration. Indeed, assume by contradiction that S contains no edge of the triangle \(xyz\in \Delta \). Perform the vertex split at x such that the new vertex \(x'\) has x, y, z as its only neighbors in \(\Delta '\). Then all edges in \(S'\) that are not in S contain \(x'\), hence none of the edges xy, yz, xz is in \(S'\). But then \(S'\) contains no triangle containing \(x'\), a contradiction.

However, it is the “if” part that is important to us. We detail below, and illustrate in figures, how to choose the extendible subsurface \(S'\), according to the intersection of the closed star of the split vertex v with S relative to the two vertices in \({{\,\textrm{lk}\,}}_v\) defining the split—either by a vertex split, see Fig. 5, or by coning over a boundary interval, see Fig. 6  for illustrations.

All cases are treated similarly. Let us describe an exhaustive list of cases: we start by describing the structure of the intersection of S with the star of v.

As S is a vertex spanning subsurface, it must contain a triangle containing v, and all such triangles must be consecutive in the star of v, else v would be a singular point of S, a contradiction. Denote by C the subcomplex of S whose maximal faces are the triangles in S containing v. Then C contains also all the edges in S that contain v, as S is a subsurface. Thus, the rest of the intersection of S with the star of v, denote it by I (which may be empty), is contained in the link \({{\,\textrm{lk}\,}}_v(\Delta )\), and denote by P the minimal subcomplex of S containing I. Now, C may contain all the vertices in the link \({{\,\textrm{lk}\,}}_v(\Delta )\), but if it does not, then P is the path containing the vertices of \({{\,\textrm{lk}\,}}_v(\Delta )\setminus C\), as S contains an edge from each triangle, in particular from each triangle containing v, and S is vertex spanning. (As mentioned, P may be empty.) To summarize, \(C\cup P\) is the intersection of S with the star of v and it contains all the vertices in the star of v. The intersection \(C\cap P\) is either empty, or a point, or two points.

Now, the vertex split at v introduces a new vertex \(v'\in \Delta '\), and there are exactly two common neighbors \(x_1\) and \(x_k\) of v and \(v'\) in \(\Delta '\), both belong to \({{\,\textrm{lk}\,}}_v(\Delta )\), and the indices are according to the cyclic order along the link of v. We distinguish the following cases:

1. (1)

   If \(x_1\) and \(x_k\) are in P then we cone with \(v'\) over the boundary interval \([x_1,x_k]\) in \({{\,\textrm{lk}\,}}_v(\Delta )\), as in Fig. 6, to obtain \(S'\) from S. We are left to check that every triangle in \(\Delta '\) contains an edge in \(S'\). This is clear for all triangles not containing \(v'\). For triangles \(v'x_ix_{i+1}\) where \(1\le i\le k-1\) it follows by the coning construction. Only two triangles remain: \(vv'x_1\) and \(vv'x_k\). The first contains \(v'x_1\) and the second contains \(v'x_k\); both of these edges are in \(S'\).

2. (2)

   Else we find a suitable vertex split in S to obtain \(S'\), chosen according to which of \(x_1\) and \(x_k\) are in C, as demonstrated in Fig. 5. We detail these cases.

   1. (2a)

      \(x_1,x_k\in C\): Denote the intersection of C with the link of v, which is an interval, by \([x_{k-s},x_{1+t}]\) in the cyclic order, where \(s,t\ge 0\). Then the induced vertex split at v in S is as follows: \(x_1\) and \(x_k\) are the common neighbors of v and \(v'\) in \(S'\); \(S'\) has exactly the following triangles containing \(v'\): \(vv'x_1\), \(vv'x_k\), and \(v'x_i x_{i+1}\) for \(i\in [1,t]\cup [k-s,k-1]\); and the triangles \(vx_ix_{i+1}\in S\) for \(i\in [1,t]\cup [k-s,k-1]\) are removed. Note that all the other triangles in \(\Delta '\) containing \(v'\) have an edge in \(P\cup \{v'x_{1+t},v'x_{k-s}\}\). We conclude that every triangle in \(\Delta '\) contains an edge in \(S'\).

   2. (2b)

      \(x_1\in C\), \(x_k\in P\setminus C\): (The last case, (2c): \(x_k\in C\), \(x_1\in P\setminus C\), is treated similarly by symmetry.) Denote the intersection of C with \({{\,\textrm{lk}\,}}_v(\Delta )\), which is an interval, by \([x_{k+s},x_{1+t}]\) in the cyclic order, where \(s\ge 1\), \(t\ge 0\). Then the induced vertex split at v in S is as follows: \(x_1\) is the unique common neighbor of v and \(v'\) in \(S'\); \(S'\) has exactly the following triangles containing \(v'\): \(vv'x_1\), and \(v'x_ix_{i+1}\) for \(i\in [1,t]\); and the triangles \(vx_i x_{i+1}\in S\) for \(i\in [1,t]\) are removed. Note that all the other triangles in \(\Delta '\) containing \(v'\) have an edge in \(P\cup \{v'x_{1+t},v'v\}\). See Fig. 5 for illustration. We conclude that every triangle in \(\Delta '\) contains an edge in \(S'\). This concludes the proof of the Extension Theorem 3.2. \(\square \)

Nonextendible subcomplex. On the left, the grey subcomplex is not extendible, as the vertex split with new vertex \(x'\) on the right demonstrates

Full size image

Extension \(S\rightarrow S'\) via a vertex split. The grey triangles and grey edges are in S

Full size image

Extension \(S\rightarrow S'\) via coning over a boundary interval in the spanning subsurface S. The grey triangles and grey edges are in S

Full size image

3.2 Extension for the Cross-Cap Triangulations of the Klein Bottle

To complete the proof of Theorem 1.3 we are left to deal with vertex splits over the four cross-cap triangulations of K. In each of the four, ABC is a noncontractible cycle; see Fig. 7. Notice that each of these four triangulations is a connected sum of two \(\mathbb RP^2\)’s along the triangle ABC; this triangle can be part of the spanning disc in each \(\mathbb RP^2\).

The four cross-cap irreducible triangulations of K. The cycle ABC is noncontractible in each of them

Full size image

Our analysis depends on whether ABC survives the vertex splits or not; namely, on whether the restriction of the vertex splits to ABC is always a 3-cycle or that for some split it becomes a 4-cycle. Formally, split the vertex A (similarly for vertices B and C) into two new vertices \(A'\) and \(A''\), with two common neighbors \(x_1\) and \(x_k\) numbered in the cyclic order on \({{\,\textrm{lk}\,}}_A(\Delta )\), and where \(A'x_2\) and \(A''x_{k+1}\) are edges in \(\Delta '\). If both B and C are in the interval \([x_1,x_k]\), then the induced complex on \(A'BC\) is a 3-cycle and we name \(A'=A\) and say that ABC survived the split. Else,^{Footnote 2} if both B and C are in the complementary closed interval \([x_k,x_1]\), then the induced complex on \(A''BC\) is a 3-cycle and we name \(A''=A\) and say that ABC survived the split. Else, the induced complex on \(A'A''BC\) is a 4-cycle and we say that ABC did not survive the split.

Case 1: ABC survives the vertex splits. Then the resulted triangulation of K is again a connected sum of two \(\mathbb RP^2\)’s along ABC, and ABC can be taken as a triangle in each of the two spanning discs of the two \(\mathbb RP^2\)’s, e.g. by taking the star of B as the spanning disc in either of the two irreducible triangulations of \(\mathbb RP^2\) (according to the vertex labels in Fig. 7) and extend from there along vertex splits. Then, the connected sum of those two discs is a vertex spanning planar simplicial complex.^{Footnote 3} Indeed, to see that the connected sum is planar, first embed the first disc in the plane, and denote by \(F\subseteq {\mathbb {R}}^2\) the image of the face ABC. Then remove the interior of F, and now embed the second disc minus the interior of ABC in F. Putting the triangle ABC back does not change the graph (but destroys planarity), and gives a strongly connected 2-complex, proving the graph is 2-rigid.

Case 2: ABC does not survive the vertex splits. Then some vertex split induced also a vertex split of the cycle ABC, making it a 4-cycle. We will show in Proposition 4.1 a reduction to the case where the first vertex split induces a split on ABC, making it a 4-cycle.

If C splits first (resp. A or B), choose S to be a spanning pinched disc at C (resp. A or B)^{Footnote 4}; see Fig. 8 (resp. Fig. 9 or Fig. 10).

Spanning pinched discs at C in the cross-cap irreducible triangulations of K

Full size image

Spanning pinched discs at A in the cross-cap irreducible triangulations of K

Full size image

Spanning pinched discs at B in the cross-cap irreducible triangulations of K

Full size image

After the first split we can resolve the singularity and choose \(S'\) to be a spanning cylinder; see Fig. 11  for illustration. Formally, in Proposition 3.3 below we describe how to resolve a singularity in a spanning pinched surface S under certain conditions; these conditions are met for the surfaces S chosen in the irreducible cross-cap triangulations of the Klein bottle (see Figs. 8, 9, and 10).

Resolving a singularity: from a pinched disc to a cylinder

Full size image

The Extension Theorem 3.2 shows that further splits (after the first split and resolving the singularity) preserve admitting a spanning cylinder. This completes the proof of the Main Theorem 1.3, modulo Propositions 3.3 and 4.1.

Next we explain how to resolve a singularity. Let \(\Gamma \) be a k-cycle in the 1-skeleton (graph) of \(\Delta \). A vertex split on \(\Delta \) is called \(\Gamma \)-elongating if it induces a vertex split on \(\Gamma \), thus, making it a \((k+1)\)-cycle. Precisely, if the vertex split at v is defined by the two vertices \(x_1\) and \(x_k\) in \({{\,\textrm{lk}\,}}_v(\Delta )\), then it is \(\Gamma \)-elongating if (u, v, w) is a path in \(\Gamma \), and \(u,w\in {{\,\textrm{lk}\,}}_v(\Delta )\) satisfy that one of them is in the interior of the interval \([x_1,x_k]\) in \({{\,\textrm{lk}\,}}_v(\Delta )\) and the other one is in the interior of the complementary interval in \({{\,\textrm{lk}\,}}_v(\Delta )\). Then after the split at v, which introduces the new vertex \(v'\), (u, v, w) is no longer a path, but \((u,v',v,w)\) is, so \((\Gamma {\setminus } \{uv\}) \cup \{v',uv',v'v\}\) is a \((k+1)\)-cycle in \(\Delta '\).

Proposition 3.3

Let \(\Delta \) be a triangulated closed surface and let S be vertex spanning pinched surface with exactly one singular vertex v. Let \(\Gamma \subseteq \Delta \) be a cycle, \(v\in \Gamma \), such that x and y are the neighbors of v in \(\Gamma \). Suppose that S contains all of the triangles in the star of v in \(\Delta \) except for those which are incident with either of the edges vx and vy, and that S contains none of the edges in \({{\,\textrm{lk}\,}}_v(\Delta )\) incident with either of x and y. Then:

1. (i)

   Every \(\Gamma \)-elongating vertex split of \(\Delta \) at v induces a vertex split of S at v that yields an extendible spanning simplicial surface \(S'\) of the resulted complex \(\Delta '\).

2. (ii)

   If S is a pinched disc then \(S'\) from part (i) is a cylinder.

Proof

Denote the cycle \({{\,\textrm{lk}\,}}_v(\Delta )\) by \((x,x_2,\dots ,y_2,y,y_1,\dots ,x_1,x)\) in cyclic order. By assumption, the edges in the intersection of S with the cycle \({{\,\textrm{lk}\,}}_v(\Delta )\) are exactly those in the two disjoint intervals \([x_2,y_2]\) and \([y_1,x_1]\). In particular, as S is a pinched surface, at v, not containing vx nor vy, the six vertices \(x,x_1,x_2,y,y_1,y_2\) are distinct.

Denote by a and b the two common neighbors of v and \(v'\) in \(\Delta '\). As the vertex split is \(\Gamma \)-elongating, w.l.o.g. the path \((y,v,v',x)\) is contained in \(\Delta '\) and \(a\in [y_1,x_1]\) and \(b\in [x_2,y_2]\).

Then the induced vertex split of S at v yields \(S'\) with the following triangles containing v or \(v'\): \(vv'a,vv'b\), vst for consecutive vertices (in \({{\,\textrm{lk}\,}}_v(\Delta )\)) \(s,t\in [y_1,a]\cup [b,y_2]\), and \(v'st\) for consecutive vertices (in \({{\,\textrm{lk}\,}}_v(\Delta )\)) \(s,t\in [x_2,b]\cup [a,x_1]\).

Then \(S'\) is indeed extendible, namely \(S'\) contains an edge from every triangle of \(\Delta '\): the only triangles in \(\Delta '\) containing v or \(v'\) that are not in \(S'\) are \(v'x_1x,v'xx_2,vy_2y\) and \(vyy_1\); they contain the following edges of \(S'\) resp.: \(v'x_1,v'x_2,vy_2\) and \(vy_1\). To complete the proof of part (i) we verify that \(S'\) is a surface with boundary—indeed, the link of \(v'\) (resp. v) in \(S'\) is the path \((x_2,\dots ,b,v,a,\dots ,x_1)\) (resp. \((y_1,\dots ,a,v',b,\dots ,y_2)\)), where the dots \(\ldots \) refer to the cyclic order in \({{\,\textrm{lk}\,}}_v(\Delta )\).

For part (ii) note that \(S'\) is homeomorphic to S union a small disc with center at v (in the realization space \(|\Delta |\)); for S a pinched disc at v this union is a cylinder. \(\square \)

As promised, the following proposition reduces the treatment of triangulations of the Klein bottle obtained from one of the cross-cap triangulations, to the case where the first split makes the empty triangle ABC a 4-cycle.

Proposition 4.1

Let \(\Delta \) be obtained from one of the four cross-cap triangulations of K by a sequence of t vertex splits such that the empty triangle ABC survived all the splits except for the last (t-th) split, which elongated it to an induced 4-cycle, denote it by ABCD. If \(t\ge 2\) then there exists an edge contraction in \(\Delta \), whose restriction to ABCD is trivial, namely, none of the edges in ABCD was contracted.

Proof

Let the \((t-1)\)-th vertex split at v introduce new vertex \(v'\), changing a triangulation \(\Delta ''\) of K to \(\Delta '\), and let the t-th vertex split be at say A (with \(D=A'\), similarly for splits at B or C; possibly \(v=A\)), changing \(\Delta '\) to \(\Delta \). If the edge \(v'v\in \Delta \) cannot be contracted, then \(\Delta \) contains an empty triangle \(v'vu\). However, this empty triangle was created by the t-th split, at A.

Case \(A\ne v\).   Then in \(\Delta '\) there exists the triangle \(Av'v\), and \(\Delta '\) splits at A to create an empty triangle \(A'v'v\) in \(\Delta \) (recall our notation \(D=A'\)). Thus, v and \(v'\) are consecutive in \({{\,\textrm{lk}\,}}_A(\Delta ')\) and are the two common neighbors of A and \(A'\) in \(\Delta \). However, as ABC does not survive the t-th split, v and \(v'\) must separate B and C in the cycle \({{\,\textrm{lk}\,}}_A(\Delta ')\), a contradiction.

Case \(A=v\).   Then, similarly, there exists a triangle \(Av'u\in \Delta '\), and for the t-th split at A, \(v'\) and u are the two common neighbors of A and \(A'\) in \(\Delta \), contradicting that \(v'\) and u must separate B and C in the cycle \({{\,\textrm{lk}\,}}_A(\Delta ')\). \(\square \)

Iterating the edge contractions guaranteed in Proposition 4.1 we would either reach a non-cross-cap irreducible triangulation, or end up with a triangulation that is obtained from one of the cross-cap triangulations via a single vertex split, that elongates ABC to a 4-cycle; as required to conclude the proof of the Main Theorem 1.3.

Remark 4.2

On a combinatorial level, edge contractions always do commute; however, reordering them may not preserve the topology of the complex along each step. The rest of this section makes this remark precise.

More formally, let us first set a notational convention: let \(\Delta \) be a simplicial complex (possibly of high dimension) on the vertex set \(V=\{v_{\{1\}},\dots ,v_{\{n\}}\}\), and \(\Delta '\) is obtained from \(\Delta \) by a sequence of edge contractions. Along this sequence, when we contract the edge \(v_Sv_T\) we name the “merged” vertex by \(v_{S\cup T}\) while the other vertices \(v_P\ne v_S,v_T\) keep their names. Note that S and T are disjoint subsets of [n].

Observation 4.3

(commutativity of edge contractions)   Under the above convention:

1. (0)

   A subset \(\{v_{T_1},\dots ,v_{T_m}\}\) of vertices in \(\Delta '\) is a face of \(\Delta '\) iff there exist indices \(i_j\in T_j\) such that \(\{v_{i_1},\dots ,v_{i_m}\}\) is a face in \(\Delta \). Thus,

2. (1)

   if each of \(\Delta '\) and \(\Delta ''\) is obtained from \(\Delta \) by some sequence of edge contractions, and the names of vertices are identical in \(\Delta '\) and \(\Delta ''\) then \(\Delta '=\Delta ''\).

3. (2)

   If \(\Delta '\) is obtained from \(\Delta \) by a sequence of at least two edge contractions, and the edge \(v_{\{i\}}v_{\{j\}}\in \Delta \) satisfies that \(i,j\in T\) for some vertex \(v_T\in \Delta '\), then there exists another sequence of edge contractions that starts with \(\Delta \), ends with \(\Delta '\), and the last edge contracted is of the form \(v_Iv_J\) such that \(i\in I\), \(j\in J\) (and \(T=I\cup J\)).

Proof

(0) is clear for a single edge contraction; in that case at most one of the \(T_l\)s has size two and all others are singletons. For the general case we iterate, i.e., induct on the number of edge contractions in the sequence yielding from \(\Delta \) to \(\Delta '\). (1) follows at once from (0).

(2) can be proved directly, by showing how to modify the sequence of edge contractions from \(\Delta \) to \(\Delta '\). To avoid extra notation, note that by (1) it is enough to show the claim in (2) for the one skeleta of \(\Delta \) and \(\Delta '\); for this case it is a basic fact on graph minors. \(\square \)

However, if we care about preserving the topology, or even just the homology, edge contractions may not commute. For example, start with the boundary of a tetrahedron on the vertex set \(\{1,2,3,4\}\), and iteratively at the t-th vertex split perform a stellar subdivision at the triangle \(\{1,t+2,t+3\}\) by a new vertex \(t+4\) (this splits vertex \(t+3\) say, and introduces a new empty triangle \(\{1,t+2,t+3\}\)). The resulted complex is a stacked sphere. Pick \(t\ge 2\). If we contract edges so that \(4,5,\dots ,t+4\) are identified we obtain a 2-sphere, the boundary of a tetrahedron. However, if we contract the edge 45 first we obtain two 2-spheres glued along an edge.

For higher genus g, the list of irreducible triangulations of \(M_g\) is not known, except for a few more cases [15], so the approach taken here is not applicable for high genus. Adding the empty triangles in an irreducible triangulation (every edge is contained in an empty triangle!) gives more flexibility in finding a strongly connected spanning subcomplex. This approach may be useful towards Problem 1.2.

Thom Sulanke communicated to us that he has verified, using a computer search, that all the 396784 irreducible triangulations of the two-holed torus admit a vertex spanning planar Laman graph, in favor of a Yes answer to Problem 1.2.