\documentclass[final]{FPSAC2022}
%\usepackage[utf8]{inputenc}
\usepackage{graphicx,xcolor}
%enumerate,
%amsthm,amssymb,xcolor,hyperref,graphicx}
%,comment}

%\usepackage[leqno]{amsmath}
\usepackage{tikz}
%\makeatletter
%\newcommand{\leqnomode}{\tagsleft@true}
%\newcommand{\reqnomode}{\tagsleft@false}
%\makeatother

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{thmintro}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\usepackage{latexsym}
\usepackage{amsfonts}
%\usepackage[leqno]{amsmath}
%\usepackage{tikz}
%\usepackage{float}
%\usepackage{lmodern}

% LaTeX macros for proofs. From Subhash
%\newcommand\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt
%depth 1.5pt
%        \hskip 1pt}}
%\newcommand\bbox{\hfill \quad \blackslug \medbreak}
%\def\dd{\hbox{-}}
%\def\cc{\hbox{-}\cdots\hbox{-}}
%\def\ll{,\ldots,}
%\def\cupcup{\cup\cdots\cup}
\def\cl{\rm{cl}}
\def\lk{\rm{lk}}
%\usepackage{marvosym}
%\def\longbox#1{\parbox{0.85\textwidth}{#1}}
%\newenvironment{proof}{\noindent {\bf Proof:\ }}{{\quad \blackslug
%\medbreak}}
% comment out next line to get hollow box
%\newenvironment{proof}{\noindent {\bf Proof:\ }}{{\quad $\Box$
%\medbreak}}


\usepackage[backend=bibtex]{biblatex}
\addbibresource{Spanning-Laman.bib}

\title{Vertex Spanning Planar Laman Graphs in Triangulated Surfaces}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[E.~Nevo and S.~Tarabykin]{Eran Nevo\thanks{\href{mailto:nevo@math.huji.ac.il}{nevo@math.huji.ac.il}. Partially supported by the Israel Science Foundation grants ISF-1695/15 and ISF-2480/20 and by ISF-BSF joint grant 2016288.}\addressmark{1}
 \and
 Simion Tarabykin\thanks{\href{mailto:simon.trabykin@gmail.com}{simon.trabykin@gmail.com}. Partially supported by ISF grant 1695/15.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Einstein Institute of Mathematics, Hebrew University, Jerusalem, Israel
}
%\addressmark{2}Einstein Institute of Mathematics, Hebrew University, Jerusalem, Israel}

%% put the date of submission here
\received{\today}


%\author{Maria Chudnovsky\thanks{\href{mailto:hello@world.c}{hello@world.c}. Partially supported by  NSF-EPSRC Grant DMS-2120644 and by ISF grant 2480/20.}\addressmark{1}, \and Eran Nevo\thanks{\href{mailto:hello@world.c}{hello@world.c}. Partially supported by the Israel Science Foundation grant ISF-2480/20 and by ISF-BSF joint grant 2016288.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
%\address{\addressmark{1}Princeton University, Princeton, NJ 08544, USA \\ \addressmark{2}Hebrew University, Jerusalem, Israel}

%% put the date of submission here
%\received{\today}

%\author{Maria Chudnovsky\thanks{Partially supported by  NSF-EPSRC Grant DMS-2120644 and by ISF grant 2480/20.}\\
%	Princeton University, Princeton, NJ 08544, USA
%	\\
%	\\
%	Eran Nevo\thanks{Partially supported by the Israel Science Foundation grant ISF-2480/20 and by ISF-BSF joint grant 2016288.}\\
%	Hebrew University, Jerusalem, Israel}
%
%\date {July 16, 2021; revised \today}

\abstract{We prove that every triangulation of either of the torus, projective plane and Klein bottle,  contains a vertex-spanning planar Laman graph as a subcomplex. Invoking a result of Kir{\'a}ly, we conclude that every $1$-skeleton of a triangulation of a surface of nonnegative Euler characteristic has a rigid realization in the plane using at most 26 locations for the vertices.}

\keywords{rigidity, Laman graph, surface triangulation}

\begin{document}
\maketitle

\section{Introduction}
A basic object of study in Framework Rigidity is a graph $G=(V,E)$ made of bars and joints in Eucledian space $\mathbb{R}^d$. Such a realization is given by specifying a map $p\colon V\rightarrow \mathbb{R}^d$. The pair $(G,p)$ is called a \emph{framework}. It is important, for both mathematicians and engineers, to know whether the framework $(G,p)$ is \emph{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 \emph{$d$-rigid}. If $G$ is $d$-rigid, a generic map $p \colon 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 infinitesimaly rigid framework $(G,p)$ with $p \colon 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 \colon V(G)\rightarrow A$ such that $(G,p)$ is infinitesimally rigid.

Jordan and Fekete~\cite{Fekete-Jordan} 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~\cite{Adiprasito-Nevo2020}. 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~\cite{Fogelsanger} asserts that for every $g$, every graph $G\in F(g)$ is $3$-rigid. Adiprasito and Nevo~\cite{Adiprasito-Nevo2020} 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:
\begin{problem}\label{prob:c_2(F(g))<c?}
Does there exist an absolute constant $c$ such that $c_2(F(g))\le c$ for all genus $g$?
\end{problem}
Kir{\'a}ly~\cite{Kiraly} 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~\cite[Problem 6.4]{Adiprasito-Nevo2020}.
Thus, an answer Yes to Problem~\ref{prob:c_2(F(g))<c?} would follow from an answer Yes to the following problem:
\begin{problem}\label{prob:spanning}
Does every triangulation of a surface (compact, connected, without boundary) admit a vertex spanning planar Laman graph?
\end{problem}
As mentioned, Kir{\'a}ly showed this for the $2$-sphere, denoted $S^2$.
We answer Problem~\ref{prob:spanning} in the affirmative for the surfaces of nonnegative Euler characteristic, by proving a stronger structural-topological result:
\begin{theorem}[Main Theorem]\label{thm:Main} The following holds:
\begin{enumerate}[label=(\roman*)]
\item Every triangulation of the projective plane $\mathbb{R}P^2$ contains a vertex spanning disc (as a subcomplex).

\item Every triangulation of the Torus $T$  contains a vertex spanning cylinder.

\item \label{thm:iii} Every triangulation of the Klein bottle $K$ contains a vertex spanning, planar, 
2-dimensional complex; it is either a cylinder
%or a  pinched disc,
or a connected sum of two triangulated discs along a triangle.\footnote{This connected sum may have at most two edges contained in no triangle face; 
deleting them yields a pure complex which is strongly-connected.}
\end{enumerate}
%
%
%
%strongly connected
%\footnote{A simplicial complex $\Delta$ is called \emph{strongly connected} if for every two maximal faces, $F$ and $T$ in $\Delta$, there exists a sequence of maximal faces in $\Delta$, $F=F_0,\ldots, F_t=T$ such that $|F_i\cap F_{i-1}|=|F_i|-1=|F_{i-1}|-1$ for all $1\le i\le t$. In particular, such $\Delta$ is \emph{pure}, namely, all its maximal faces have the same dimension.}
%2-complex; it is either a cylinder, or a  pinched disc, or a connected sum of two triangulated discs along a triangle.
\end{theorem}
For a topological space $M$, denote by $F(M)$ the family of $1$-skeleta of triangulations of $M$.
%Let $S^2$ denote the $2$-sphere. Then,
\begin{corollary}\label{cor:Main}
For $M\in \{T, K, \mathbb{R}P^2, S^2\}$, $c_2(M)\leq 26$.
\end{corollary}
To see that Theorem~\ref{thm:Main} implies Corollary~\ref{cor:Main}, note two facts: (i) all the vertex spanning subcomplexes in  Theorem~\ref{thm:Main} have a $2$-rigid graph (indeed, clearly all strongly-connected pure $d$-dimensional simplicial complexes have a $d$-rigid $1$-skeleton, see, \textit{e.g.},~\cite[Lemma~6.2]{Kalai:LBT}), 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 themself planar.
%, so we only have to argue for the Klein bottle and the case when the vertex spanning subcomplex found is a connected sum of two triangulated discs along a triangle. However, removing (the interior of) that gluing triangle does not change the $1$-skeleton and make the new subcomplex planar.
Now apply
Kir{\'a}ly's result that $c_2(F(PL))\le 26$~\cite{Kiraly}.

The basic idea in the proof of Theorem~\ref{thm:Main} is to use induction over \emph{vertex splits}:
%~\cite{Whiteley-VertexSplitting}:
first we find a suitable spanning subsurface in each \emph{irreducible triangulation} of $M\in \{T, K, \mathbb{R}P^2\}$, and then \emph{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 \emph{extendible}. This is defined and explained in more details in Section~\ref{sec:split}. 
In Section~\ref{sec:rearrange} we complete the proof of Theorem~\ref{thm:Main}\ref{thm:iii} via rearranging the vertex splits.
In Section~\ref{sec:prelim} we give the necessary background on rigidity and on irreducible triangulations. We end with concluding remarks in Section~\ref{sec:conclude}.


\section{Preliminaries}\label{sec:prelim}
\subsection{Rigidity}
Let $G=(V,E)$ be a graph, and let $p \colon V\rightarrow \mathbb{R}^d$ be a map.
An \emph{infinitesimal motion} of the framework $(G,p)$ is a map $a \colon 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:
\[ \langle a(v)-a(u), p(v)-p(u)\rangle =0.
\]
The motion $a$ is \emph{trivial} if the relation above is satisfied for every pair of vertices in $V$; otherwise $a$ is \emph{nontrivial}. The framework $(G,p)$ is \emph{infinitesimally rigid} if all its 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 \emph{$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 \colon V(G)\rightarrow \mathbb{R}^{d}$. The readers may consult, \textit{e.g.},~\cite{Connelly:RigiditySurvey, graver1993combinatorial} for further background on rigidity.

%\begin{lemma}[Vertex split lemma]\label{lem:Whiteley-split}
%\end{lemma}


\subsection{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\neq u\}$. This operation is called an \emph{edge contraction} at $vu$.
The inverse operation, that starts with $G'$ and produces $G$ is called a \emph{vertex split} at $u$.
Similarly one defines edge contraction (and vertex split) for simplicial complexes: 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'$.

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

\begin{theorem}[{\cite{Barnette-Edelson-Orientable,Barnette-Edelson-NonOrientable}}]\label{thm:irr-triang}
For all $g$, $M_g$ has finitely many irreducible triangulations.
 \end{theorem}
When the Euler characteristic $\chi(M_g)\geq 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, \textit{e.g.},~Whiteley~\cite{Whiteley-split} for a proof that all maximal planar graphs are $3$-rigid using this fact; $\mathbb{R}P^2$ has
 two irreducible triangulations, see Barnette~\cite{Barnette1982GeneratingTT}; the torus has
21, see Lavrenchenko~\cite{Lavrenchenko1990IrreducibleTO};
the Klein bottle has 29, see Lavrenchenko--Negami~\cite{Lawrencenko1997IrreducibleTO} and a correction by Sulanke~\cite{Sulanke2006NoteOT}.

We will use these characterizations in the proof of Theorem~\ref{thm:Main}, in the next section.




\section{Extentions}\label{sec:split}
\subsection{Extendible subsurfaces}
Informally, we want the vertex split on a triangulation of $M_g$, $\Delta\rightarrow \Delta'$, to allow an \emph{extension} $S'\subseteq \Delta'$ of the spanning disc/cylinder/\textit{etc.}\ $S\subseteq \Delta$; see Theorem~\ref{thm:Main} for the relevant topology of $S$. Formally, for a triangulation $\Delta$ of the surface $M_g$, define:

\begin{definition}\label{def:extendible}
A vertex spanning subsurface (with boundary) $S\subseteq \Delta$ is \emph{extendible} if for every vertex split $\Delta\rightarrow \Delta'$ there exists a subsurface $S'\subseteq \Delta'$ such that either
\begin{enumerate}[label=(\roman*)]
\item $S'$ is obtained from $S$ by a vertex split at the same vertex, or

\item $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$.)
\end{enumerate}
\end{definition}
Note that such $S'\subseteq \Delta'$ is vertex spanning and homeomorphic to $S$.

\begin{theorem}[Extension Theorem]\label{thm:extention}
Let $\Delta$ triangulate some surface $M_g$ (compact, connected, without boundary), and let $S\subseteq \Delta$ be a vertex
spanning subsurface. Then:

(1) $S$ is extendible in $\Delta$ if and only if it contains at least one edge
from every triangle in $\Delta$.

(2) Let $\Delta\rightarrow \Delta'$ be a vertex split. If $S$ is extendible then it has an extendible extension $S'\subseteq \Delta'$.
\end{theorem}
In all the irreducible triangulations of $\mathbb{R}P^2$, $T$ and $K$, except for the four so called cross-cap triangulations of the Klein bottle $K$ (see Figure~\ref{fig:4crosscap}), we find an extendible spanning subsurface $S$ to start with: for $\mathbb{R}P^2$ the subsurface $S$ is a disc, and for $T$ and $K$ the subsurface $S$ is a cylinder. See Figure~\ref{fig:SinRP2} for spanning discs in the two irreducible triangulation of $\mathbb{R}P^2$, and Figure~\ref{fig:SinT} for an example of a spanning cylinder in an irreducible triangulation of the torus.
\begin{figure}[h]
  \centering
  \includegraphics[width=0.6\textwidth]{Spheres in Projective Plane.png}
  \caption{Spanning discs, in grey, in the irreducible triangulations of the projective plane.}\label{fig:SinRP2}
\end{figure}

\begin{figure}[h]
  \centering
  \includegraphics[width=\textwidth]{Cylinders in Irred. torus (1-10).PNG}
  \caption{Spanning cylinders, in grey,  in 10 out of the 21 irreducible triangulations of the torus.}\label{fig:SinT}
\end{figure}
By the Extension Theorem (Theorem~\ref{thm:extention}) and induction on vertex splits, the assertion of our Main Theorem~\ref{thm:Main} holds for $\mathbb{R}P^2$ and $T$, and for all triangulations of $K$ not obtained by vertex splits starting from one of the cross-cap irreducible triangulations.

For a proof of the Extension Theorem~\ref{thm:extention},
the ``only if'' part in (1) is easy, see Figure~\ref{fig:only_if} for an illustration.
\begin{figure}[h]
  \centering
  \includegraphics[width=\textwidth]{Non extendible subcomplex copy.png}
  \caption{Non extendible subcomplex. On the left, the grey subcomplex is not extendible, as the vertex split with new vertex $x'$ on the right demonstrates.}\label{fig:only_if}
\end{figure}
However it is the ``if" part that is important to us.
We 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$, in some cases -- either by a vertex split, see Figure~\ref{fig:extend-via-split}, or by coning over a boundary interval, see Figure~\ref{fig:extend-via-coning}.
\begin{figure}[h]
  \centering
  \includegraphics[scale=3, width=\textwidth]{Extension theorem - case 2b copy.png
  %Extension theorem - case 4A.png
  }
  \caption{Extension $S\rightarrow S'$ via vertex split. The grey triangles and grey edges are in $S$.}\label{fig:extend-via-split}
\end{figure}

\begin{figure}[h]
  \centering
  \includegraphics[width=\textwidth]{Extension theorem - case 1 (big indices) copy.png}
  \caption{Extension $S\rightarrow S'$ via coning over boundary interval in the spanning subsurface $S$. The grey triangles and grey edges are in $S$.}\label{fig:extend-via-coning}
\end{figure}

All cases are treated similarly, let us  describe an exhaustive list of cases:  the intersection of $S$ with the star of $v$, consists of (i) a subcomplex $C$ of consecutive triangles, each of them contains $v$ (this collection is nonempty as $v\in S$, and it may exhaust the star), and of (ii) a path $P$ in the link of $v$, such that $C\cup P$ contains all the vertices in the star of $v$ (as $S$ contains an edge from each triangle and is vertex spanning, and $P$ may be empty).
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 the link of $v$, and the indices are according to the cyclic order along the link of $v$. We distinguish the following cases: (1) if $x_1$ and $x_k$ are in $P$, then we cone as in Figure~\ref{fig:extend-via-coning}; (2) else we find a suitable vertex split, chosen according to which of $x_1$ and $x_k$ are in $C$, as demonstrated in Figure~\ref{fig:extend-via-split}.

\subsection{Extension for the cross-cap triangulations of the Klein bottle}
To complete the proof of Theorem~\ref{thm:Main} 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 Figure~\ref{fig:4crosscap}.

\begin{figure}[h]
  \centering
  \includegraphics[page=1,width=0.8\textwidth]{Irreducible Crosscap Type Klein with distinguished 3-cylce copy.png}
  \caption{The four cross-cap irreducible triangulations of $K$. The cycle $ABC$ is  noncontractible in each of them.}\label{fig:4crosscap}
\end{figure}
Notice that each of these four triangulations is a connected sum of two $\mathbb{R}P^2$'s along the triangle $ABC$; this triangle can be part of the spanning disc in each $\mathbb{R}P^2$.

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 $\lk_A(\Delta)$, and where $A'x_2$ and $A''x_{k+1}$ are edges in $\Delta'$.
%we consider the induced complex on $A',B,C$.
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$ \emph{survived} the split. Else, 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$ \emph{survived} the split. Else, the induced complex on $A'A''BC$ is a $4$-cycle and we say that $ABC$ did \emph{not survive} the split.

\textbf{Case 1: $ABC$ survives the vertex splits.} Then the resulted triangulation of $K$ is again a connected sum of two $\mathbb{R}P^2$'s along $ABC$, and we observe that $ABC$ can be taken as a triangle in each of the two spanning discs of the two $\mathbb{R}P^2$'s.
The connected sum of those two discs is a planar 2-dimensional simplicial complex.

\textbf{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 prove that the vertex splits can be rearranged such that the first one splits $ABC$, making it a $4$-cycle, see Proposition~\ref{prop:ABCsplitsFirst}.

If $C$ splits first (similarly for $A$ and $B$), choose $S$ to be a spanning pinched disc at $C$; see Figure~\ref{fig:pinched_disc}.
%\eran{put Fig.p.93}
\begin{figure}[h]
  \centering
\includegraphics[width=0.7\textwidth]{pinched disc at c copy.png}
\caption{Spanning pinched discs at $C$ in a cross-cap irreducible triangulations of $K$.}\label{fig:pinched_disc}
\end{figure}
After the first split we can resolve the singularity and choose $S'$ to be a spanning cylinder; see Figure~\ref{fig:resolve-singularity} for illustration.
\begin{figure}[h]
  \centering
\includegraphics[width=\textwidth]{Singularity resolving extension copy.png}
\caption{Resolving a singularity: from a pinched disc to a cylinder.}\label{fig:resolve-singularity}
\end{figure}
The Extension Theorem (Theorem~\ref{thm:extention}) shows that further splits preserve admitting a spanning cylinder.
This completes the (sketch of) proof of the main Theorem~\ref{thm:Main} modulo Proposition~\ref{prop:ABCsplitsFirst}.

\section{Rearranging vertex splits}\label{sec:rearrange}
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 missing triangle $ABC$ a $4$-cycle.
\begin{proposition}\label{prop:ABCsplitsFirst}
Let $\Delta$ be obtained from one of the four cross-cap triangulations of $K$ by a sequence of $t$ %topology-preserving
vertex splits such that the missing 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, non of the edges in $ABCD$ was contracted.
\end{proposition}
\begin{proof}[Proof sketch]
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 a missing triangle $v'vu$. However, this missing triangle was created by the $t$-th split, at $A$. If $A\neq v$ one shows it implies that $v$ and $v'$ are consecutive in $\lk_A(\Delta')$. However, as $ABC$ does not survive the $t$-th split, $v$ and $v'$ must separate $B$ and $C$ in the cycle $\lk_A(\Delta')$, a contradiction.
One argues similarly when $A=v$.
\end{proof}


\begin{remark}
On a combinatorial level, edge contractions always \emph{do} commute; however, reordering them may \emph{not} preserve the topology of the complex.
\end{remark}
%%%%%%
More formally, let us first set a notational convention: let $\Delta$ be a simplicial complex on the vertex set $V=\{v_{\{1\}},\ldots,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\neq v_S,v_T$ keep their names. Note that $S$ and $T$ are disjoint subsets of $[n]$.
\begin{observation}[Commutativity of edge contractions]\label{obs:edge_contractions_commute}
Under the above convention:
%
A subset $\{v_{T_1},\ldots,v_{T_m}\}$ of vertices in $\Delta'$ is a face of $\Delta'$ if and only if there exist indices $i_j\in T_j$ such that $\{v_{i_1},\ldots,v_{i_m}\}$ is a face in $\Delta$. Thus:
\begin{enumerate}[label=(\roman*)]
\item 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''$.


\item If $\Delta'$ is obtained from $\Delta$ by a sequence of 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  contracts the edge $v_{\{i\}}v_{\{j\}}$ first (resp.~last).
\end{enumerate}
\end{observation}
%%%
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 trianlge $\{1,2,t+3\}$ by a new vertex $t+4$.
The resulted complex is a stacked sphere. Pick $t\ge 5$. If we contract edges so that $4,5,\ldots, t+3$ 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.

\section{Concluding remarks}\label{sec:conclude}
Sulanke~\cite{Sulanke-All} found all irreducible triangulations for a few more surfaces of small genus.
For higher genus $g$, the list of irreducible triangulations of $M_g$ is not known, so the approach taken here is not applicable. 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~\ref{prob:spanning}, and could be checked first on Sulanke's database~\cite{Sulanke-Some}.

%\textbf{All $d$-rigid graphs.}
%Let $F_d(n)$ be the family of all $d$-rigid graphs on $n$ vertices. Kir{\'a}ly~\cite{Kiraly} showed that as $n$ tends to infinity  $c_2(F_2(n))=\Theta(\sqrt(n))$ (the lower bound $\Omega(\sqrt(n))$ was proved earlier by Jordan and Fekete~\cite{Jordan-Fekete}).
%
%\begin{problem}\label{prob:F_d(n)}
%Let $d\ge 3$. Is $c_d(F_d(n))=o(n)$?
%\end{problem}
%The lower bound $c_d(F_d(n))=\Omega(n^{1/d})$ follows as in the case $d=2$, see \textit{e.g.}~\cite{Adiprasito-Nevo2020}.
%
\printbibliography
\end{document}
