# Projective plane graphs and 3-rigidity

E. Kastis and S.C. Power  Dept. Math. Stats.
Lancaster University
Lancaster LA1 4YF
U.K<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

A ${\mathcal{P}}$-graph is a simple graph $G$ which is embeddable in the real
projective plane ${\mathcal{P}}$. A $(3,6)$-tight ${\mathcal{P}}$-graph is
shown to be constructible from one of 8 uncontractible ${\mathcal{P}}$-graphs
by a sequence of vertex splitting moves. Also it is shown that a
${\mathcal{P}}$-graph is minimally generically 3-rigid if and only if it is
$(3,6)$-tight. In particular this characterisation holds for graphs that are
embeddable in the Möbius strip.

2010 Mathematics Subject Classification. 52C25 51E15
Key words and phrases: projective plane, embedded graphs, geometric rigidity
This work was supported by the Engineering and Physical Sciences Research
Council [EP/P01108X/1]

##  1\. Introduction

Let $G$ be the graph of a triangulated sphere. Then an associated bar-joint
framework $(G,p)$ in ${\mathbb{R}}^{3}$ is known to be minimally rigid if the
placements $p(v)$ of the vertices $v$ is strictly convex (Cauchy [4]) or if
the placement is generic. The latter case follows from Gluck’s result [12]
that any generic placement is in fact infinitesimally rigid. An equivalent
formulation of Gluck’s theorem asserts that if $G$ is a simple graph which is
embeddable in the sphere then $G$ is minimally 3-rigid if and only if it
satisfies a $(3,6)$-tight sparsity condition. We obtain here the exact
analogue of this for simple graphs that are embeddable in the real projective
plane ${\mathcal{P}}$. The proof rests on viewing these graphs as partial
triangulations and deriving inductive arguments based on edge contractions for
certain admissible edges. Accordingly we may state this result in the
following form. An immediate corollary is that this combinatorial
characterisation also holds for triangulated Möbius strips.

A graph $G$ is _3-rigid_ if its generic bar-joint frameworks in
${\mathbb{R}}^{3}$ are infinitesimally rigid and is _minimally 3-rigid_ if no
subgraph has this property.

######  Theorem 1.1.

Let $G$ be a simple graph associated with a partial triangulation of the real
projective plane. Then $G$ is minimally $3$-rigid if and only if $G$ is
$(3,6)$-tight.

Recall that a $(3,6)$-tight graph $G=(V,E)$ is one that satisfies the Maxwell
count $|E|=3|V|-6$ and the sparsity condition $|E^{\prime}|\leq
3|V^{\prime}|-6$ for subgraphs $G^{\prime}$ with at least 3 vertices. In
particular it follows from the Maxwell condition that such a graph falls 3
edges short of a full (possibly nonsimple) triangulation of ${\mathcal{P}}$.
The proof of Theorem 1.1 depends heavily on our main result, Theorem 6.1,
which is a purely combinatorial constructive characterisation of the
${\mathcal{P}}$-graphs which are (3,6)-tight. A key step is the identification
of edge contraction moves, for certain edges that lie in two 3-cycle faces,
such that the $(3,6)$-sparsity condition is preserved. This is done in Section
3 by exploiting the implicit topological structure of the graphs. The
associated contraction sequences must terminate and the terminal graphs are
said to in _irreducible_. They have the defining property that every
contractible edge lies on a critical $4$-, $5$\- or $6$-cycle. For the
remainder of the proof of Theorem 6.1 we show that an irreducible graph has no
contractible edges (Section 5) and we determine the uncontractible graphs
(Section 4). Determining the uncontractibles requires an extensive case-by-
case analysis leading to the 8 “base” graphs given in Figures 3, 4, 5.

The determination of construction schemes and their base graphs for various
classes of graphs is of general interest, both for embedded graph theory and
for the rigidity of bar-joint frameworks. We note, for example, that Barnette
[1] employed vertex splitting moves for the construction of triangulations of
2-manifolds and showed that there are 2 (full) triangulations of
${\mathcal{P}}$ which are uncontractible. Also, Barnette and Edelson [2], [3]
have shown that all 2-manifolds have finitely many minimal uncontractible
triangulations. Our construction theorem is in a similar spirit to this and we
expect our reduction methods, involving critical cycles and minimum hole
incidence degree, for example, to be useful for more general surface graphs
and for other sparsity classes. In particular, for $(3,6)$-tight
${\mathcal{P}}$-graphs we show that the irreducibles are the uncontractibles
and it would be interesting to determine to what extent this phenomenon is
true for other surfaces and sparsity classes.

We define a _triangulated surface graph_ associated with a classical surface
${\mathcal{M}}$, with or without boundary and we represent embeddings of these
graphs, and their connected subgraphs (${\mathcal{M}}$-graphs), in terms of
_face graphs_. A face graph is a finite connected planar graph with a
specified pairing of some or all of the edges in the outer boundary.
Identifying the paired edges gives an identification graph $G=(V,E)$ together
with a set $F$ of facial 3-cycles inherited from the finite planar graph. See
Definitions 2.1, 2.2. In Section 3 we identify the obstacles, in terms of
critical cycles of edges, which prevent edge contraction moves from preserving
the sparsity condition. The determination in Section 4 of the 8 uncontractible
${\mathcal{P}}$-graphs is given in several stages, based on the nature of the
“holes” in their partial triangulation. They may have one hole with 6-cycle
boundary, two holes with boundary cycle lengths 5 and 4, or three holes, each
with a 4-cycle boundary. Also we give a useful index for the successive
determination of these uncontractible base graphs, namely the minimum hole
incidence degree $h(G)$ (Definition 4.3).

Since Whiteley’s demonstration [14] that vertex splitting preserves generic
rigidity this construction move has become an important tool in combinatorial
rigidity theory [11]. See for example the more recent studies of generic
rigidity in the case of graphs for modified spheres [7], [8], [5], [13], and
in the case of a partially triangulated torus [6]. The proof of Theorem 1.1
given in Section 6 follows quickly from Whiteley’s theorem, Theorem 6.1, and
the 3-rigidity of the 8 base graphs.

##  2\. Graphs in Surfaces

Let ${\mathcal{M}}$ be a classical surface, possibly with boundary. Then a
_surface graph for ${\mathcal{M}}$_ is a triple $G=(V,E,F)$ where $(V,E)$ is a
simple graph, $F$ is a set of $3$-cycles of edges, called facial 3-cycles, and
where there exists a faithful embedding of $G$ in ${\mathcal{M}}$ for which
the facial 3-cycles correspond to the 3-sided faces inthe embedding. A surface
graph for ${\mathcal{M}}$, which we also refer to as an ${\mathcal{M}}$-graph,
can thus be viewed as a simple graph obtained from a full triangulation of
${\mathcal{M}}$ by discarding vertices, edges and faces. Also, $G$ is a
_triangulated surface graph for ${\mathcal{M}}$_ if the union of the embedded
faces is equal to ${\mathcal{M}}$. The following equivalent definition, based
on simplicial complexes rather than surfaces, is combinatorial and so more
elementary.

######  Definition 2.1.

A _triangulated surface graph_ is a graph $G=G(M)=(V,E,F)$ which is simple and
is determined by the $1$-skeleton and the $2$-simplexes of a finite simplicial
complex $M$ where $M$ has the following properties.

  1. (i)

$M$ consists of a finite set of $2$-simplexes $\sigma_{1},\sigma_{2},\dots$
together with their $1$-simplexes and $0$-simplexes.

  2. (ii)

Every $1$-simplex lies in at most two $2$-simplexes.

Condition (i) implies that each 1-simplex lies in at least one 2-simplex. It
follows that $M$ can be viewed as a _combinatorial surface_ and we define
${\mathcal{M}}={\mathcal{M}}(M)={\mathcal{M}}(G)$ to be the classical
topological surface, possibly with boundary, which is determined by $M$, the
simplicial complex [9]. Evidently, $G$ is a triangulated surface graph for
${\mathcal{M}}$.

Classical compact surfaces are classified up to homeomorphism by combinatorial
surfaces and, moreover, combinatorial surfaces arise from triangulated polygon
graphs (also called triangulated discs) by means of an identification of
certain pairs of boundary edges [9].

We now formally define such labelled triangulated discs which we refer to as
_face graphs_.

######  Definition 2.2.

A _face graph_ for a triangulated surface graph is a pair $(B,\lambda)$ where
$B$ is the planar graph of a triangulated disc and $\lambda$ is a partition of
the _boundary graph_ $\partial B$ of $B$, such that each set of the partition
has $1$ or $2$ edges, and the paired edges of the partition are directed.

A face graph $(B,\lambda)$ defines a simplicial complex $M$, with
$1$-simplexes provided by edges and identified edge pairs, and 2-simplexes
provided by the facial 3-cycles. Also, if the boundary graph of $B$ is a
3-cycle and $\lambda$ is trivial then this 3-cycle defines a 2-simplex of $M$.
If the identification graph $G=B/\lambda$ is a simple graph then $M$ is of the
type given in Definition 2.1, and so $G$ is a triangulated surface graph
$G=(V,E,F)$.

###  2.1. ${\mathcal{M}}$-graphs

We are concerned simple graphs that can be embedded in a connected classical
surface ${\mathcal{M}}$. More precisely we shall be concerned with embedded
graphs, which we refer to as ${\mathcal{M}}$-graphs, or surface graphs, and we
can define them directly in terms of more general face graphs
$(B_{0},\lambda)$, where $B_{0}\subseteq B$ with $\partial B\subset B_{0}$ and
$(B,\lambda)$ is as in the previous definition. Thus a surface graph has the
form $G=B_{0}/\lambda$ where $B_{0}$ is obtained from $B$ by the removal of
the interior edges of $k$ interior-disjoint triangulated subdiscs of $B$. We
refer to $k$ as the _number of holes_ of the embedded graph $G$. When $k=1$ we
refer to $B_{0}$ as an _annular face graph_.

$e$$f$$g$$e$$f$$g$$v_{1}$$v_{2}$$v_{3}$$v_{1}$$v_{2}$$v_{3}$

Figure 1. A face graph $(B_{0},\lambda)$ for a ${\mathcal{P}}$-graph.

Figure 1 shows the annular face graph $(B_{0},\lambda)$ for a surface graph
$G=B_{0}/\lambda$. The labelling of outer boundary edges and vertices
determines how pairs of edges are identified. A planar triangulation of the
interior of the inner 6-cycle gives a face graph $(B,\lambda)$ for the
triangulated surface graph $S=B/\lambda$, if and only if $S$ is simple. In
view of the identifications the topological surface ${\mathcal{M}}(S)$ is the
real projective plane ${\mathcal{P}}$ and $G$ is a ${\mathcal{P}}$-graph.

In this example the surface graph $G$ happens to be a (fully) triangulated
surface graph for the Möbius strip. However, in general a surface graph may
have “exposed” edges, that is, edges that belong to no facial 3-cycles, and so
in this case the surface graph will not be a triangulated surface graph for
any classical surface with boundary.

##  3\. Contraction moves and (3,6)-sparsity.

Let $G=(V,E,F)$ be a surface graph. An edge of $G$ is of type $FF$ if it is
contained in two facial $3$-cycles and an $FF$ edge is _contractible_ if it is
not contained in any non-facial $3$-cycle. For such an edge $e=uv$ there is a
natural contraction move $G\to G^{\prime}$ on the graph $G$, corresponding to
a contraction of $e$, merging $u$ and $v$ to a single vertex, leading to a
surface graph $G^{\prime}=(V^{\prime},E^{\prime},F^{\prime})$ where
$|V^{\prime}|=|V|-1,|E^{\prime}|=|E|-3,|F^{\prime}|=|F|-2$. We also say that
$G$ is _contractible_ if it has a contractible $FF$ edge.

To define formally the contracted graph $G^{\prime}$, let $e=vw$ be a
contractible $FF$ edge in $G$ and let $avw$ and $bvw$ be the two facial
3-cycles which contain $e$. Then $G^{\prime}$ is obtained from $G$ by an _edge
contraction_ on $e=vw$ if $G^{\prime}$ is obtained by (i) deleting the edges
$aw$ and $bw$, (ii) replacing all remaining edges of the form $xw$ with $xv$,
(iii) deleting the edge $e$ and the vertex $w$. That $G^{\prime}$ is simple
follows from the fact that a contractible $FF$ edge does not lie on a
nonfacial 3-cycle.

Given an edge contraction move $G\to G^{\prime}$ we note that the inverse
move, recovering $G$ from $G^{\prime}$, is a _vertex splitting move_ at $v$
which in particular introduces a new vertex $w$ and the new $FF$ edge $vw$.
Such vertex splitting move $G^{\prime}\to G$, which might be thought of as
being locally planar, creates the new surface graph $G$ for the surface
${\mathcal{M}}$ from a given surface graph $G^{\prime}$ for ${\mathcal{M}}$.

###  3.1. (3,6)-sparse ${\mathcal{P}}$-graphs.

If $G=(V,E)$ is a graph then its _freedom number_ is defined to be
$f(G)=3|V|-|E|$. A graph $G$ is _$(3,6)$ -sparse_ if $f(G^{\prime})\geq 6$ for
any subgraph $G^{\prime}$ with at least 3 vertices, and is _$(3,6)$ -tight_ if
it is $(3,6)$-sparse and $f(G)=6$. In particular a $(3,6)$-sparse graph is a
simple graph, with no loop edges and no parallel edges.

Let $B$ be a triangulated disc such that the boundary cycle $\partial B$ is of
even length $2r$. With the pairing partition $\lambda$ of opposite edges,
directed in cyclic order, the pair $(B,\lambda)$ is a face graph. If
$S=B/\lambda$ is simple then $S$ is a triangulated surface graph for the real
projective plane ${\mathcal{P}}$. Also we observe that the freedom number
$f(B)$ is equal to $6+(2r-3)$. This follows since $B$ may be viewed as a
triangulated sphere (which has freedom number $6$) with $2r-3$ edges removed.
Noting that $S$ is related to $B$ by the loss of $r$ vertices and $r$ edges it
follows that

$f(S)=(3+2r)-3r+r=3.$

Let $G$ be a surface graph for ${\mathcal{P}}$, the real projective plane,
which is determined by the annular face $(B_{0},\lambda)$ where the inner
boundary cycle of edges has length $s$. Then $f(G)=f(S)-(s-3)$ and in
particular $G$ satisfies the so-called _Maxwell count_ $f(G)=6$ if and only if
$s=6$.

######  Lemma 3.1.

Let $G$ be a triangulated surface graph for the Möbius strip. Then $G$ is a
surface graph for ${\mathcal{P}}$. Also $G$ satisfies the Maxwell count if and
only if the boundary graph $\partial G$ is the graph of a simple 6-cycle.

###### Proof.

Let $G(M)=(V,E,F)$ be a triangulated surface graph given by a finite
simplicial complex $M$ for the Möbius strip, as in Definition 2.1. Then $G(M)$
is determined by a face graph $(B,\mu)$ where $\mu$ is obtained from an
identification of two vertex-disjoint paths in the boundary of $B$, which have
the same length and orientation and which have end vertices $w_{1},w_{2}$ and
$w_{3},w_{4}$ respectively. In Figure 2 the boundary of $B$ is depicted as
rectangular.

$w_{1}$$w_{2}$$w_{3}$$w_{4}$$v_{1}$$v_{2}$$B$

Figure 2. A Möbius strip triangulated surface graph as a ${\mathcal{P}}$ with
hole graph.

Augment the planar graph $B$ to obtain a containing planar graph $B_{1}$ which
has 2 additional vertices, $v_{1}$ and $v_{2}$ say, and additional edges
$v_{1}w$ (resp. $v_{2}w$) which are incident to vertices on the boundary path
from $w_{4}$ to $w_{1}$ (resp. $w_{2}$ to $w_{3}$). This defines a
triangulated disc $B_{1}$ which is also indicated in Figure 2. Define a
partition $\lambda$ for $B_{1}$ as the augmentation of $\mu$ by the two
directed edge pairs $v_{1}w_{1},v_{2}w_{3}$ and $w_{2}v_{2},w_{3}v_{1}$ and
let $(B_{1},\lambda)$ be the resulting face graph. Then $H=B_{1}/\lambda$ is a
triangulated surface graph for ${\mathcal{P}}$. Moreover, the faces of $H$
that are incident to the vertex $v_{1}=v_{2}$ in $S$ are the faces of a
triangulated disc and $G$ is a surface graph for ${\mathcal{P}}$. ∎

Let $G$ be a ${\mathcal{P}}$-graph, with $k$ holes. If $G$ satisfies the
Maxwell count $f(G)=6$ then $k=1,2$ or $3$. For $k=1$ a representing face
graph $(B_{0},\lambda)$ for $G$ is annular with a 6-cycle inner boundary. This
inner boundary can intersect and even coincide with the outer boundary of $B$.
For $k=2$ there are two inner boundaries of length $5$ and $4$ corresponding
to the boundaries of the interior disjoint discs defining $G$, while for $k=3$
there are three inner boundaries which are 4-cycles. In particular,
$3\leq|\partial G|\leq 12.$

######  Definition 3.2.

For $k=1,2,3$ the set ${\mathfrak{P}}_{k}$ is the set of $(3,6)$-tight
${\mathcal{P}}$-graphs which have $k$ holes.

While a surface graph is a graph with extra structure we shall informally
refer to the elements of ${\mathfrak{P}}_{k}$ as graphs.

###  3.2. When contracted graphs are $(3,6)$-tight

A contraction move $G\to G^{\prime}$ on a contractible $FF$ edge $e$ of a
surface graph preserves the Maxwell count but need not preserve
$(3,6)$-tightness. We now examine this more closely in the case of a surface
graph for the real projective plane ${\mathcal{P}}$.

Suppose that $G_{1}\subseteq G$ and that both $G_{1}$ and $G$ are in
${\mathfrak{P}}_{1}$. If $e$ is a contractible $FF$ edge of $G$ which lies on
the boundary graph of $G_{1}$ then, since $G_{1}$ contains only one of the
facial 3-cycles incident to $e$, the contraction $G\to G^{\prime}$ for $e$
gives a contraction $G^{\prime}$ which is not $(3,6)$-sparse, since
$f(G_{1}^{\prime})=5$. We shall show that the failure of any contraction to
preserve $(3,6)$-sparsity is due to such a subgraph obstacle.

The following general lemma, which we refer to as the filling in lemma, is
useful for the identification of maximal $(3,6)$-tight subgraphs with specific
properties. See also [6]. In particular this lemma plays a role in the
identification of an obstacle subgraph.

######  Lemma 3.3.

Let $G\in{\mathfrak{P}}_{1}$ and let $H$ be an embedded triangulated disc
graph in G.

(i) If $K$ is a $(3,6)$-tight subgraph of $G$ with $K\cap H=\partial H$ then
$\partial H$ is a $3$-cycle graph.

(ii) If $K$ is a $(3,6)$-sparse subgraph of $G$ with $f(K)=7$ and $K\cap
H=\partial H$ then $\partial H$ is either a $3$-cycle or $4$-cycle graph.

###### Proof.

(i) Write $H^{c}$ for the subgraph of $G$ which contains the edges of
$\partial H$ and the edges of $G$ not contained in $H$. Since $G=H^{c}\cup H$
and $H^{c}\cap H=\partial H$ we have

$6=f(G)=f(H^{c})+f(H)-f(\partial H).$

Since $f(H^{c})\geq 6$ we have $f(H)-f(\partial H)\leq 0$. On the other hand,

$6\leq f(K\cup H)=f(K)+f(H)-f(\partial H)$

and $f(K)=6$ and so it follows that $f(H)-f(\partial H)=0$. It follows that
$\partial H$ is a 3-cycle.

(ii) The argument above leads to $-1\leq f(H)-f(\partial H)$ and hence to the
inequality $-1\leq f(D)-f(\partial D)$. This implies that $\partial H$ is
either a $3$-cycle or $4$-cycle graph. ∎

######  Lemma 3.4.

Let $G\in{\mathfrak{P}}_{1}$, let $e$ be a contractible $FF$ edge in $G$, and
let $G^{\prime}$ be the simple graph arising from the contraction move $G\to
G^{\prime}$ associated with $e$. Then either $G^{\prime}\in{\mathfrak{P}}_{1}$
or $e$ lies on the boundary of a subgraph $G_{1}$ of $G$ where
$G_{1}\in{\mathfrak{P}}_{1}$.

###### Proof.

Assume that $G^{\prime}\notin{\mathfrak{P}}_{1}$. It follows that $G^{\prime}$
must fail the $(3,6)$-sparsity count. Thus there exists a subgraph $K$ of $G$
containing $e$ for which the edge contraction results in a graph $K^{\prime}$
satisfying $f(K^{\prime})<6$. Let $e=vw$ and let $c$ and $d$ be the facial
$3$-cycles which contain $e$. If both $c$ and $d$ are subgraphs of $K$ then
$f(K)=f(K^{\prime})<6$, which contradicts the sparsity count for $G$. Thus $K$
must contain at most one of these facial $3$-cycles.

_Case 1_. Suppose first that $K$ is a maximal subgraph among all subgraphs of
$G$ which contain the cycle $c$, do not contain $d$, and for which contraction
of $e$ results in a simple graph $K^{\prime}$ which fails the $(3,6)$-sparsity
count. Note that $f(K)=f(K^{\prime})+1$ which implies $f(K)=6$ and
$f(K^{\prime})=5$. In particular, $K$ is $(3,6)$-tight, and is a connected
graph.

Let $(B_{0},\lambda)$ be a face graph for $G$ with an associated face graph
$(B,\lambda)$ for a triangulated surface graph for $S=(V,E,F)$ for
${\mathcal{P}}$ containing $G$. In particular $(B,\lambda)$ provides a
faithful topological embedding $\pi:S\to{\mathcal{P}}$. Let
$X(K)\subset{\mathcal{P}}$ be the closed set $\pi(E(K))$ and let
$\tilde{X}(K)$ be the union of $X(K)$ and the embeddings of the faces for the
facial $3$-cycles belonging $K$. Finally, let $U_{1},\dots,U_{n}$ be the
maximal connected open sets of the complement of $\tilde{X}(K)$ in
${\mathcal{P}}$.

Note that each such connected open set $U_{i}$ is determined by a set
${\mathcal{U}}_{i}$ of embedded faces of $S$ with the property: each pair of
embedded faces of $U_{i}$ are the endpoints of a path of edge-sharing embedded
faces in ${\mathcal{U}}_{i}$. From the topological nature of ${\mathcal{P}}$
it follows that $U_{i}$ has one of the following 3 properties.

(i) $U_{i}$ is an open disc.

(ii) $U_{i}$ is the interior of a Möbius strip.

(iii) The complement of $U_{i}$ is not connected.

The third property cannot hold since the embedding of $K$ is contained in the
complement of $U_{i}$ and contains the boundary of $U_{i}$, and yet $K$ is a
connected graph.

From the second property it follows that $K$ is a planar graph, since it can
be embedded in the complement of $U_{i}$ and this is a triangulated disc. This
is also a contradiction, since the edge contraction of a contractible $FF$
edge in a planar triangulated graph preserves $(3,6)$-sparsity.

Each set $U_{i}$ is therefore the interior of the closed set determined by an
embedding of a triangulated disc graph in $B$, say $H(U_{i})$. (Indeed, the
facial 3-cycles defining $H(U_{i})$ are those whose torus embedding have
interior set contained in $U_{i}$.) We may assume that $U_{1}$ is the open set
that contains the hole of $G$. (More precisely, $U_{1}$ contains the open set
corresponding to the embedded faces for the triangulated disc in $B$ that
determines $B_{1}$.)

For $i>1$ by the filling in lemma, Lemma 3.3, it follows that $\partial
H(U_{i})$ is a 3-cycle. By the maximality of $K$ we have $k=1$ (since adding
the edges and vertices of $S$ interior to these nonfacial 3-cycles gives a
subgraph of $G$ with the same freedom count). Thus, $K$ is a subgraph of $G$
and is equal to the surface graph for ${\mathcal{P}}$ defined by $B$ and the
embedded triangulated disc $H(U_{1})$. Thus, with $G_{1}=K$, the proof is
complete in this case.

_Case 2._ It remains to consider the case for which $K$ contains neither of
the facial $3$-cycles which contain $e$. Thus $f(K)=f(K^{\prime})+2$ and
$f(K)\in\\{6,7\\}$. Once again we assume that $K$ is a maximal subgraph of $G$
with respect to these properties and consider the complementary components
$U_{1},\dots,U_{k}$. As before each set $U_{i}$ is homeomorphic to a disc and
determines an embedded triangulated disc graph $H(U_{i})$, one of which, say
$H(U_{1})$, contains the triangulated disc which defines $G$. The filling in
lemma and maximality now implies that each boundary of $H(U_{i})$, for $i>1$,
is a $4$-cycle. By the maximality of $K$, we see once again that $k=1$ (since
adding the missing edge for such a $4$-cycle gives a subgraph of $G$ with a
lower freedom count) and the proof is completed as before. ∎

The filling in lemma holds for graphs in
${\mathfrak{P}}_{2},{\mathfrak{P}}_{3}$, with the same proof, and we may
extend Lemma 3.4 to these families of graphs.

######  Lemma 3.5.

Let $G\in{\mathfrak{P}}_{k}$, for $k=1,2$ or $3$, let $e$ be a contractible
$FF$ edge in $G$, and let $G^{\prime}$ be the simple graph arising from the
contraction move $G\to G^{\prime}$ associated with $e$. Then either
$G^{\prime}\in{\mathfrak{P}}_{k}$ or $e$ lies on the boundary of a subgraph
$G_{1}$ of $G$ where $G_{1}\in{\mathfrak{P}}_{l}$, for some $1\leq l\leq k$.

###### Proof.

The proof follows the same pattern as in the case $k=1$. Thus we assume that
$G^{\prime}\notin{\mathfrak{P}}_{k}$ and consider a subgraph $K$ of $G$ which
is maximal amongst all subgraphs which do not contain one (or both, according
to Cases 1 and 2) of the facial 3-cycles incident to $e$ and whose contraction
$K^{\prime}$ has freedom number $f(K^{\prime})=5$ (or $4$). We consider the
open set which is the complement of the embedding in ${\mathcal{P}}$ of $K$
and its facial 3-cycles. (The embedding here is denoted $\tilde{X}(K)$ in the
case $k=1$.) This open set has components $U_{1},\dots,U_{n}$ and each is the
interior of a union of an edge-connected set of ${\mathcal{P}}$-embedded
facial 3-cycles of $S$.

It follows as before, from the topological nature of ${\mathcal{P}}$, from
$(3,6)$-sparsity and from the filling in lemma, that each $U_{j}$ is an open
disc. Moreover, in the case $k=2$ each $U_{j}$ contains at least one of the 2
discs $D_{1},D_{2}$ which defines $G$ and so $n$ is 1 or 2 and it follows that
$K$ belongs to ${\mathfrak{P}}_{n}$, as desired. Similarly, for $k=3$, each
$U_{j}$ contains at least one of the 3 discs $D_{1},D_{2},D_{3}$ which defines
$G$ and so $n$ is 1, 2 or 3 and $K$ belongs to ${\mathfrak{P}}_{l}$ for some
$1\leq l\leq 3$. ∎

##  4\. The uncontractibles

Let $k=1,2$ or $3$. By the finiteness of a graph $G$ in ${\mathfrak{P}}_{k}$
it is evident that it admits a full reduction sequence

$G=G_{1}\to G_{2}\to\dots\to G_{n}$

where (i) each graph is in ${\mathfrak{P}}_{k}$, (ii) each move $G_{k}\to
G_{k+1}$ is an edge contraction for an $FF$ edge, as before, and (iii) $G_{n}$
is _irreducible_ in ${\mathfrak{P}}_{k}$ in the sense that it admits no edge
contraction to a graph in ${\mathfrak{P}}_{k}$.

Let us say that a surface graph is _uncontractible_ is every $FF$ edge lies on
a nonfacial 3-cycle. An uncontractible graph $G\in{\mathfrak{P}}_{k}$ is
certainly an irreducible graph in ${\mathfrak{P}}_{k}$ but we show in the next
section that the two classes coincide. In Section 4.2 we shall prove that
there are 8 uncontractible graphs but first we establish some useful
properties of the irreducible graphs.

###  4.1. Some properties of irreducible graphs

We say that a $k$-cycle of edges in $G$, $c$ say, is a _planar $k$-cycle_ in
$G$ if there is a face graph $(B_{0},\lambda)$ for $G$, with containing face
graph $(B,\lambda)$ for the triangulated surface graph $B/\lambda$ for
${\mathcal{P}}$, such that $c$ is determined by the boundary cycle $\hat{c}$
of a triangulated disc $D$ in $B$. Note that the holes of $G$ are defined by
embedded triangulated discs $D_{i}$ in $B_{0}$, and so we may say that a
planar cycle $c$ in $G$ _contains a hole of $G$_ if $D$ contains such an
embedded disc $D_{i}$. Also we may say that $c$ _properly contains a hole_ if
there is such an inclusion which is proper.

The following lemma shows that an irreducible (3,6)-tight
${\mathcal{P}}$-graph contains no degree 3 vertex that is incident to an $FF$
edge or lies on a planar nonfacial triangle.

######  Lemma 4.1.

Let $G$ be a graph in ${\mathfrak{P}}_{k}$, for $k=1,2$ or $3$.

(i) If $e$ is an $FF$ edge incident to a degree 3 vertex then
$G/e\in{\mathfrak{P}}_{k}$.

(ii) If $v$ is an interior vertex of $G$ and $v$ lies on a planar nonfacial
3-cycle then there is a contractible edge $vw$ with
$G/vw\in{\mathfrak{P}}_{k}$.

###### Proof.

For (i) note that since $G$ is simple $e$ is a contractible edge. Write $e=uv$
with facial 3-cycles $uvx$ and $uvy$, with $\deg v=3$. Then $e$ cannot lie on
a critical 4-, 5- or 6-cycle since one of the edges incident to $u$ would
provide an interior chord for this cycle. Also $e$ does not lie on a nonfacial
3-cycle and so (i) follows.

For (ii) let $H$ be the triangulated disc subgraph induced by the faces
incident to $v$, with vertices $v_{1},\dots,v_{n}$ in cyclic order on the
boundary of $H$. Considering the hypothesis, and relabelling, we may assume
that there is an edge $f=v_{1}v_{j}$ with $3\leq j\leq n-2$ so that the edges
$v_{3}v_{4},v_{4}v_{5},\dots,v_{j-1}v_{j},f$ are the boundary edges of a
triangulated disc. It is straightforward to show that one of the vertices
$v_{2},\dots,v_{j-1}$ has degree 3, and so (i) applies. ∎

The next lemma shows that if $G$ is irreducible then there is no critical
$m$-cycle which properly contains an $m$-hole.

######  Lemma 4.2.

Let $G$ be a graph in ${\mathfrak{P}}_{k}$, for $k=1,2$ or $3$, such that
there is a critical $m$-cycle, for $m=1,2$ or 3, which properly contains an
$m$-cycle hole, so that $G=G_{1}\cup A$ where $A$ is the annular graph
determined by the two $m$-cycles. Then $G$ is constructible from $G_{1}$ by
planar vertex splitting moves.

###### Proof.

Fix $k$ and $m\leq k$. Suppose that $|V(G)|=|V(G_{1})|+1.$ Then there is a
degree $3$ vertex on the boundary of the relevant hole of $G$. By Lemma 4.1(i)
$G$ is constructible from $G_{1}$ by a single planar vertex splitting move.
Assume next that the lemma is true whenever $|V(G)|=|V(G_{1})|+j$, for
$j=1,2,\dots,N-1$, and suppose that $|V(G)|=|V(G_{1})|+N$. Let $e$ be an
interior edge of the annular graph $A$. If the contraction $G/e$ is in
${\mathfrak{P}}_{m}$ then it follows from the induction step that $G$ is
constructible from $G_{1}$ by planar vertex splitting moves. So, by Lemma 3.5
we may assume (i), that $e$ lies on a critical $m$-cycle, with associated
graph $G^{\prime}$, or (ii), that $e$ lies on a nonfacial 3-cycle of $G$. In
the former case we may take $G_{1}^{\prime\prime}$ to be the union of $G_{1}$
and $G_{1}^{\prime}$. Then $G_{1}^{\prime\prime}$ is also in
${\mathfrak{P}}_{k}$. Since $|V(G_{1}^{\prime\prime})|-|V(G_{1})|<N$ and
$|V(G)|-|V(G_{1}^{\prime\prime})|<N$ it follows from the induction step that
the lemma holds for $G$ and $G_{1}$. So we may assume that (ii) holds, and
moreover, in view of Lemma 4.1(ii), that $e$ lies on a nonplanar nonfacial
3-cycle. To complete the proof we observe that this is not possible when $e$
is incident to a vertex on the hole which is not a vertex of the critical
$m$-cycle. ∎

###  4.2. The uncontractible graphs.

We now identify 8 uncontractible $(3,6)$-tight ${\mathcal{P}}$-graphs. Figure
3 gives two uncontractibles specified by face graphs and Figure 4 gives three
further uncontractibles as embedded graphs in ${\mathcal{P}}$. Here
${\mathcal{P}}$ is represented as a disc or a rectangle, with diagonally
opposite points of the boundary identified. The 3 remaining irreducibles are
given in Figure 5. The notation $G^{h}_{n}$ indicates that $n$ is the number
of vertices and $h=h(G)$ is the minimum _hole incidence degree_ given in the
following definition.

Figure 3. The uncontractible graphs $G^{2}_{3}\in{\mathfrak{P}}_{1}$ and
$G^{3}_{4}\in{\mathfrak{P}}_{3}$.

Figure 4. The uncontractible graphs $G^{0}_{7},$ $G^{2}_{6,\alpha}$ and
$G^{2}_{6,\beta}$ in ${\mathfrak{P}}_{3}$.

Figure 5. The uncontractible graphs $G^{1}_{5}$ in ${\mathfrak{P}}_{2}$ and
$G^{1}_{6,\alpha},$ $G^{1}_{6,\beta}$in ${\mathfrak{P}}_{3}$.

######  Definition 4.3.

Let $v$ be a vertex of $G=(V,E,F)\in{\mathfrak{P}}_{k}$ for some $k=1,2,3$.
Then (i) $\deg_{F}(v)$ is the number of facial 3-cycles incident to $v$, (ii)
$\deg_{h}(v)=\deg(v)-\deg_{F}(v)$ is the _hole incidence degree_ for $v$, and
(iii) $h(G)$ is the minimum hole incidence degree,
$h(G)=\min_{v}\operatorname{deg}_{h}(v)$.

In what follows, we shall usually consider graphs as ${\mathcal{P}}$-graphs,
with facial structure. However, let us note that as graphs: $G^{2}_{3}$ is the
triangle graph $K_{3}$; $G_{4}^{3}$ is $K_{4}$; $G_{7}^{0}$ is the cone graph
over $K_{3,3}$; $G_{5}^{1}$ is $K_{5}-e$. Also the four remaining graphs, each
with 6 vertices, are depletions of $K_{6}$ by 3 edges where these edges (i)
form a copy of $K_{3}$, (ii) are disjoint, (iii) have one vertex shared by 2
edges, (iv) have 2 vertices of degree 1. These graphs account for all possible
$(3,6)$-tight graphs on $n$ vertices for $n=3,4,5,6$, together with 1 of the
26 such graphs for $n=7$. (We remark that for $n=8,9,10$ the number of
$(3,6)$-tight graphs rises steeply, with values 375, 11495, 613092 [10].)

######  Proposition 4.4.

Let $G$ be an uncontractible graph in ${\mathfrak{P}}_{k}$, for $k=1,2$ or
$3$, which has an interior vertex. Then $k=3$ and $G$ is the hexagon graph
$G^{0}_{7}$.

###### Proof.

Let $z$ be an interior vertex in $G$. Let $X(z)$ be the subgraph of $G$
induced by $z$ and its neighbours. Assume that $z$ has degree $n$ and label
its neighbours, in cyclical order, as $v_{1},v_{2},\dots,v_{n}$. Then $X(z)$
has $n$ edges that are incident to $z$, plus $n$ perimeter edges
$v_{1}v_{2},v_{2}v_{3},\dots,v_{n}v_{1}$, and additional edges between non-
adjacent vertices $v_{1},\dots,v_{n}$. Since $G$ is uncontractible there exist
at least $\left\lceil\frac{n}{2}\right\rceil$ additional edges. It follows now
from the (3,)-sparsity that $\operatorname{deg}z=n\geq 6$. Also, since $G$ is
uncontractible there can be no vertices $v_{i}$ of degree $3$, since otherwise
the $FF$ edge $zv_{i}$ would be a contractible edge. For the same reason each
vertex $v_{i}$ has at least one additional edge $v_{i}v_{j}$ for some $j$.

Suppose that there is an additional edge $v_{i}v_{j}$ such that the
(nonfacial) 3-cycle $zv_{i}v_{j}z$ is a planar 3-cycle. Then $G$ contains a
triangulated disc $D$ with 3-cycle boundary with at least 4 vertices. Such a
graph $D$ has a contractible $FF$ edge with an interior vertex and so this
edge is also contractible in $G$, a contradiction.

Consider one of the additional edges, $v_{i}v_{j}$ with $i<j$, and let
$i^{\prime}\in\\{i+1,\dots,j-1\\}$. We claim that for every additional edge
$v_{i^{\prime}}v_{j^{\prime}}$ we have $j^{\prime}\notin\\{i+1,\dots,j-1\\}$.
Indeed, if this is not the case then there is a non-facial planar 3-cycle $c$
described by the edges
$zv_{i^{\prime}},v_{i^{\prime}}v_{j^{\prime}},v_{j^{\prime}}z$ and by the
previous paragraph this is a contradiction. Thus the additional edges have
this _non-nested_ property. It follows by a simple inductive argument that the
embedded graph $X(z)$ has faces with boundary cycles of length at most 4 since
otherwise there must be perimeter vertices of degree 3. These 4-cycles are
planar 4-cycles and so by Lemma 4.2 there are 3 holes. Thus $n=6$ and $G$ is
the hexagon graph $G^{0}_{7}$. ∎

The next lemma is key to the determination of the uncontractible graphs in
${\mathfrak{P}}_{k}$ for $k=2$ or $3$.

######  Lemma 4.5.

Let $G\in{\mathfrak{P}}_{k}$, for $k=2$ or 3, be an uncontractible (3,6)-tight
graph with no interior vertex and let $v_{1}$ be a vertex with
$\operatorname{deg}_{h}(v_{1})=1$ which lies on the boundary of a 4-cycle hole
of $G$ with edges $v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{1}$. Then
$\operatorname{deg}(v_{1})=4$ if $v_{1}$ is not adjacent to $v_{3}$ and
$\operatorname{deg}(v_{1})=5$ otherwise.

###### Proof.

Let $v_{2}=w_{1},w_{2},\dots,w_{n}=v_{4}$ be the neighbours of $v_{1}$ in
cyclical order. Since $\operatorname{deg}_{h}(v_{1})=1$, we also have the
edges $w_{1}w_{2},\dots,w_{n-1}w_{n}$. Note that $\deg(v_{1})\geq 4$ since if
the degree is 3 then the edge $v_{1}w_{2}$ is contractible.

Case (a). $v_{3}\neq w_{i}$, for every $i\in\\{2,\dots,m-1\\}$.
Suppose that $n\geq 5$. It follows from the uncontractibility that for each
vertex $w_{i},2\leq i\leq n-1,$ there is an associated edge $w_{i}w_{r}$ for
some $1\leq r\leq n$ and an associated edge $w_{i+1}w_{s}$ for some $s>r$.
Since there are at most 3 holes there is an edge $w_{i}w_{i+1}$ for which the
associated cycle through $w_{i},w_{i+1},w_{s},w_{r}$ is triangulated by faces.
We claim that (i) it is a 4-cycle and (ii) it is triangulated by 2 faces. Note
that at most one of the edges $w_{i}w_{s},w_{i+1}w_{r}$ exists. Indeed,
although we can have $K_{4}\to{\mathcal{P}}$ with 3 faces this implies the
existence of a degree 3 vertex and hence a contractible edge incident to it, a
contradiction. If the face of the triangulation which contains $w_{i}w_{i+1}$
has third vertex $w$ not equal to $w_{s}$ or $w_{r}$, then at least one of the
edges $w_{i}w$, $w_{i+1}w$ is contractible, a contradiction. Since an interior
vertex $w$ does not exist the implied cycle is a 4-cycle and (i) and (ii)
hold.

Since $G$ is uncontractible $w_{i}w_{i+1}$ lies in a non-facial 3-cycle. Since
$v_{1}w_{j}$ is also an $FF$ edge for every $j\in\\{2,\dots,n-1\\}$, it
follows that there are just two candidate non-facial 3-cycles:
$w_{i-1}w_{i}w_{i+1}w_{i-1}$ or $w_{i}w_{i+1}w_{i+2}w_{i}$.

(i):

If $w_{i}w_{i+1}$ lies on the cycle $w_{i-1}w_{i}w_{i+1}w_{i-1}$, then the
4-cycle $w_{i-1}v_{1}w_{r}w_{i+1}w_{i-1}$ contains strictly the hole boundary
$v_{1}v_{2}v_{3}v_{4}v_{1}$, contradicting Lemma LABEL:l:4holelemma. Note that
this 4-cycle does contain the hole in our sense since the shading in Figure 6
indicates a triangulated disc in ${\mathcal{P}}$ with boundary equal to this
4-cycle.

$v_{1}$$w_{n}$$w_{r}$$w_{i+1}$$w_{i}$$w_{i-1}$$w_{1}$$v_{3}$ Figure 6. The
4-cycle $w_{i-1}v_{1}w_{r}w_{i+1}w_{i-1}$ contains strictly the 4-hole
$v_{1}v_{2}v_{3}v_{4}v_{1}$.

(ii):

If $w_{i}w_{i+1}$ lies on the cycle $w_{i}w_{i+1}w_{i+2}w_{i}$, then, noting
that $w_{i+2}w_{i}$ is an edge, we claim that the 5-cycle
$w_{i}v_{1}w_{r}w_{i+1}w_{i+2}w_{i}$ contains all the holes, which is a
contradiction. To see this note that by Lemma 4.2 the 4-cycle
$v_{1}w_{r}w_{i}w_{i+2}v_{1}$ contains no holes. See Figure 7.

$v_{1}$$w_{n}$$w_{r}$$w_{i+1}$$w_{i+2}$$w_{i}$$w_{1}$$v_{3}$ Figure 7. The
5-cycle $w_{i}v_{1}w_{r}w_{i+1}w_{i+2}w_{i}$ contains all the holes.

Hence none of the edges $w_{2}w_{3},w_{3}w_{4},\dots,w_{n-2}w_{n-1}$ is an
$FF$ edge. Also, the same holds for the edge $v_{2}w_{2}$, since it cannot lie
in no non-facial 3-cycle. Thus every edge of the form
$v_{2}w_{2},w_{2}w_{3},w_{3}w_{4},\dots,w_{n-1}w_{n}$ is on the boundary of a
hole. Since every edge $v_{1}w_{j}$ is an $FF$ edge, $j=2,\dots,n-1$, it
follows that $G$ contains at least $\left\lceil\frac{n}{2}+1\right\rceil$
holes. Thus, $n=4$.

Case (b). $v_{4}=w_{i_{0}}$, for some $i_{0}\in\\{2,\dots,n-1\\}$.
We have $\operatorname{deg}(v)\geq 5$ since $G$ is a simple graph. Suppose
that $n\geq 6$. As in case (a) we may assume that there exists an $FF$ edge
$w_{i}w_{i+1}$ with $i>1$ and $i+1<i_{0}$, and with vertex $w_{r}$ as before.
(See Figure 8.) Then, the only possible non-facial 3-cycle for $w_{i}w_{i+1}$
is $v_{3}w_{i}w_{i+1}v_{3}$. However, this would lead to a contradiction since
the 4-cycle $w_{i}v_{3}v_{4}v_{1}w_{i}$ strictly contains the hole
$v_{1}v_{2}v_{3}v_{4}v_{1}$.

.

$v_{1}$$v_{4}$$v_{2}$$v_{3}$$w_{i}$$w_{r}$$w_{i+1}$$v_{3}$ Figure 8. The
4-cycle $v_{4}v_{3}v_{1}w_{i}v_{4}$ contains strictly the 4-hole
$v_{1}v_{2}v_{3}v_{4}v_{1}$.

Thus, each $w_{i}w_{i+1}$ is not an $FF$ edge. Similarly, we can argue that
such a 4-cycle would be created if $w_{i_{0}-1}w_{i_{0}}$ was an $FF$ edge.
Thus again we have that $w_{1}w_{2}$ is not an $FF$ edge, since it does not
lie on a non-facial 3-cycle. Thus, the edges
$w_{1}w_{2},w_{2}w_{3},w_{3}w_{4}$ should lie on the boundaries of different
holes, which again contradicts the number of the holes of $G$. Thus
$\operatorname{deg}(v_{1})=5$. ∎

######  Proposition 4.6.

Let $G\in{\mathfrak{P}}_{k}$, for $k=1,2$ or 3, be an uncontractible
(3,6)-tight graph with no interior vertex. If there exists a vertex $v_{1}\in
V(G)$ with $\operatorname{deg}_{h}(v_{1})=1$ then $G$ is one of the graphs
$G^{1}_{6,\alpha},G^{1}_{6,\beta},G^{1}_{5}$.

###### Proof.

Case (a). Assume first that $v_{1}$ lies on the 4-cycle boundary of the hole
$H_{1}$, with vertices $v_{1},v_{2},v_{3},v_{4}$, and let
$v_{2}=w_{1},w_{2},\dots,w_{n}=v_{4}$ be all the neighbours of $v_{1}$. Since
$\operatorname{deg}_{h}(v_{1})=1$ the edges $w_{1}w_{2},\dots,w_{n-1}w_{n}$
exist. Also $\operatorname{deg}(v_{1})\geq 4$ since otherwise $v_{1}w_{2}$ is
a contractible $FF$ edge. There are two subcases.

(i):

$v_{3}\neq w_{i}$, for every $i\in\\{1,2,\dots,m\\}$.
By Lemma 4.5 we have $\operatorname{deg}(v_{1})=4$. By the uncontractibility
of the edges $v_{1}w_{2}$ and $v_{1}w_{3}$ the edges $w_{2}w_{4}$ and
$w_{1}w_{3}$ must exist. Thus $G$ contains the graph in Figure 9, except
possibly for the edge $v_{3}w_{3}$. It follows that the 4-cycle
$w_{1}w_{2}w_{4}w_{3}w_{1}$ must be the boundary of a 4-hole $H_{2}$, since
otherwise the 5-cycle $v_{1}w_{1}w_{3}w_{2}w_{4}v_{1}$ contains all the holes,
in the sense, as before, of being the boundary of an embedded disc, $B$ say,
which contains the holes. This contradicts $(3,6)$-tightness. We claim now
that the edge $v_{3}w_{2}$ or $v_{3}w_{3}$ must exist, for otherwise there is
a contractible edge in $B$. To see this check that since
$\operatorname{deg}(v_{3})\geq 3$, there exists a vertex $z$ in the interior
of the 5-cycle $v_{3}w_{4}w_{2}w_{3}w_{1}v_{3}$, such that $v_{3}z\in E(G)$.
Since $v_{3}z$ does not lie on a non facial 3-cycle, it follows that it lies
on the boundary of the third 4-hole. Thus, if $v_{3}w_{3}$ is not allowed, we
may assume by symmetry that $w_{1}z$ is an $FF$ edge in $E(G)$, so it lies on
the non-facial 3 cycle $w_{1}zw_{2}w_{1}$. Hence the third hole is described
by the 4-cycle $w_{4}v_{3}zw_{1}w_{4}$. However, this implies that $zw_{3}\in
E(G)$, which is a contractible $FF$ edge, so we have proved the claim. Hence
without loss of generality $G$ contains the subgraph $G^{1}_{6,\alpha}$ as
indicated in Figure 9. Since $G$ is uncontractible it follows that
$G=G^{1}_{6,\alpha}$.

$v_{1}$$w_{4}$$w_{3}$$w_{2}$$w_{1}$$v_{3}$ Figure 9. The uncontractible graph
$G^{1}_{6,\alpha}$.

(ii):

$v_{3}=w_{i_{0}}$ for some $i_{0}\in\\{3,\dots,n-2\\}$.
By Lemma 4.5 $\operatorname{deg}(v_{1})=5$ and so $v_{3}=w_{3}$. Since
$v_{1}w_{2}$ is an $FF$ edge, it follows that $w_{2}w_{4}\in E(G)$ and so $G$
contains the graph $G=G^{1}_{6,\beta}$ of Figure 10. Since $G$ is
uncontractible it follows that this subgraph is equal to $G$.

$v_{1}$$v_{4}$$w_{4}$$w_{2}$$v_{2}$$v_{3}$ Figure 10. The uncontractible graph
$G^{1}_{6,\beta}$.

Case (b). Let $v_{1}$ lie on the boundary of a 5-hole $H$ with boundary edges
$v_{1}v_{2}$, $v_{2}v_{3}$, $v_{3}v_{4}$, $v_{4}v_{5}$, $v_{5}v_{1}$. We may
assume that $\operatorname{deg}_{h}(v_{i})=2$, for every $i=2,3,4,5$, since
otherwise there is a vertex $v$ on a 4-hole of $G$. Since $G$ has two holes it
is straightforward to check that $\operatorname{deg}(v_{1})=4$ and that the
second hole is described by the 4-cycle $v_{2}v_{3}v_{5}v_{4}v_{2}$. Thus we
obtain that $G$ is the uncontractible (3,6)-tight given by Figure 11.

$v_{1}$$v_{5}$$v_{4}$$v_{3}$$v_{2}$ Figure 11. The uncontractible graph
$G^{1}_{5}$.

∎

Note that in the proof of the previous result we have determined the
uncontractible graphs in 2-holed case and shown that there is a unique
uncontractible graph, namely $G_{5}^{1}$. The next proposition completes the
proof that there are 8 base graphs.

######  Proposition 4.7.

Let $G\in{\mathcal{P}}$ be an uncontractible (3,6)-tight graph with
$\operatorname{deg}_{h}(v)\geq 2$ for all $v\in V(G)$. Then $G$ is one of the
four graphs $G^{2}_{6,\alpha},G^{2}_{6,\beta},G^{3}_{4},G_{3}^{2}$.

###### Proof.

Suppose first that $G$ has 2 or 3 holes. Then the hole boundaries have length
4 or 5 and it follows from the simplicity of the graph that every vertex is
common to at least 2 holes. Since there are either 2 or 3 holes it follows
that $|V|\leq 6$.

Case (a). Suppose that $G$ contains at least one $FF$ edge, say $v_{1}v_{2}$,
with non facial 3-cycle $v_{1}v_{2}v_{3}$, and associated 3-cycle faces
$v_{1}v_{2}v_{4}v_{1}$ and $v_{1}v_{2}v_{5}v_{1}$. We claim that one of the
edges $v_{3}v_{4}$ or $v_{3}v_{5}$ lies in $E(G)$. Suppose, by way of
contradiction, that neither edge exists. Then we show that the edge
$v_{4}v_{5}$ is also absent. Indeed, if $v_{4}v_{5}\in E(G)$, then we have two
planar 5-cycles; $v_{1}v_{4}v_{5}v_{2}v_{3}v_{1}$ and
$v_{1}v_{5}v_{4}v_{2}v_{3}v_{1}$, as in Figure 12.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

Figure 12. A subgraph with the 5-cycles $v_{1}v_{4}v_{5}v_{2}v_{3}v_{1}$ and
$v_{1}v_{5}v_{4}v_{2}v_{3}v_{1}$.

By the sparsity condition one of these has a vertex in the interior with 3
incident edges and the other has a single chordal edge in the interior and by
symmetry we may assume that the planar 5-cycle
$v_{1}v_{4}v_{5}v_{2}v_{3}v_{1}$ has the single chordal edge. However, of the
5 possibilities $v_{1}v_{2},v_{2}v_{4},v_{1}v_{5}$ are not available, by the
simplicity of $G$, and the edges $v_{3}v_{4},v_{3}v_{5}$ are absent by
assumption. This contradiction shows that $v_{4}v_{5}$ is indeed absent and
so, since $v_{4},v_{5}$ have degree at least 2, the edges
$v_{4}v_{6},v_{5}v_{6}$ must exist. Now the complement of the 2 3-cycle faces
is bounded by two 6-cycles. By the sparsity condition there are now only 2
further edges to add and so there must be a 5-cycle hole, a contradiction, and
so the claim holds.

Without loss of generality we suppose that $v_{3}v_{4}\in E(G)$. Since
$\operatorname{deg}_{h}(v_{2})\geq 2$, it follows that $v_{2}v_{6}\in E(G)$.
Moreover, the edges $v_{6}v_{2}$,$v_{2}v_{3}$ should be on the boundary of a
planar 4-hole $H_{1}$, and this implies that $v_{1}v_{6}\in E(G)$. Similarly
we obtain that the two remaining holes are determined by the cycles
$v_{1}v_{3}v_{4}v_{5}v_{1}$, and $v_{2}v_{5}v_{4}v_{6}v_{2}$. The resulting
(3,6)-tight triangulated surface graph is given in Figure 13 and is the
uncontractible graph $G_{6,\alpha}^{2}$.

$v_{5}$$v_{2}$$v_{3}$$v_{1}$$v_{4}$$v_{6}$ Figure 13. The uncontractible graph
with $h(G)=2$ and an $FF$ edge; $G_{6,\alpha}^{2}$.

Case (b). Suppose now $G$ has at least one 3-cycle face, $v_{1}v_{2}v_{3}$,
and no $FF$ edges. Then the edge $v_{1}v_{2}$ is on the boundary of a 4-hole
$H_{1}$, that is determined by the edges $v_{1}v_{2}$, $v_{2}v_{4}$,
$v_{4}v_{5}$ and $v_{5}v_{1}$.

To see that $|V|\neq 5$ note that without loss of generality the edge
$v_{3}v_{4}$ exists and $G$ contains the subgraph shown in Figure 14. Also,
since $v_{5}$ cannot have degree 2 at least one of the edges
$v_{5}v_{3},v_{5}v_{2}$ exists.

$v_{1}$$v_{2}$$v_{4}$$v_{5}$$v_{4}$$v_{5}$$v_{3}$

Figure 14. A necessary subgraph.

If $v_{5}v_{2}$ exists then the edge $v_{2}v_{3}$ is adjacent to a 4-cycle
hole and $v_{5}v_{3}$ is absent. We note next that the planar 5-cycle
$v_{3}v_{1}v_{5}v_{2}v_{4}v_{3}$ must contain a chord edge (and so provide the
third 4-cycle hole). The only available edge (by simplicity) is $v_{3}v_{5}$.
This however is inadmissible since it introduces a second 3-cycle face
$v_{3}v_{5}v_{1}$ adjacent to $v_{1}v_{2}v_{3}$.

Similarly, if $v_{5}v_{3}$ exists then we have the planar 6-cycle
$v_{3}v_{1}v_{5}v_{3}v_{2}v_{4}v_{3}$ and there must exist a diameter edge to
create the 2 additional 4-cycle holes. As there is no such edge we conclude
that $|V|=6$.

Introducing $v_{6}$ the fact that $v_{2}v_{3}$ and $v_{3}v_{1}$ lie on 4-cycle
hole boundaries leads to the graph $G_{6,\beta}^{2}$ indicated in Figure 15.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{6}$$v_{4}$$v_{5}$ Figure 15. The
uncontractible graph $G_{6,\beta}^{2}$, with $h(G)=2$, no $FF$ edge and a
3-cycle face.

Case (c). Let now $G$ be a graph with no 3-cycle faces. Since
$\operatorname{deg}(v)\geq 3$ for each vertex it follows that
$\operatorname{deg}_{h}(v)=3$ and $\deg(v)=3$, for all $v\in V(G)$. Thus
$|V|=4$ and it follows that $G$ is the uncontractible (3,6)-tight graph
$G_{4}^{3}$ given by Figure 16.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{2}$$v_{3}$$v_{4}$ Figure 16. The
uncontractible graph $G_{4}^{3}$ with $h(G)=3$.

Case (d). Finally, suppose that $G\in\mathfrak{P}_{1}$. We claim that the
graph has no faces and the surface graph is given by Figure 19.

Assume first that there exists an $FF$ edge, say $v_{1}v_{2}$, that lies on
the faces $v_{1}v_{2}v_{3}v_{1}$ and $v_{1}v_{2}v_{4}v_{1}$. Since the graph
is uncontractible, $v_{1}v_{2}$ lies on a non facial 3-cycle
$v_{1}v_{2}v_{5}v_{1}$. Note that $v_{3}v_{4}\notin E(G)$, since otherwise the
6-hole would lie inside a 5-cycle, either $v_{1}v_{3}v_{4}v_{2}v_{5}v_{1}$ or
$v_{1}v_{4}v_{3}v_{2}v_{5}v_{1}$, contradicting the sparsity of the graph. It
follows that we cannot have $|V(G)|\leq 5$. Indeed, in this case (see Figure
17) $v_{3}v_{5}\in E(G)$, since $\operatorname{deg}(v_{3})\geq 3$, and so
without loss of generality, in view of the symmetry, $v_{1}v_{3}$ is an $FF$
edge. But this edge does not lie on a non-facial 3-cycle, a contradiction.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{5}$ Figure 17. $|V(G)|\leq 5$ leads to
a contradiction.

Thus $|V(G)|=6$ and it remains to consider two subcases:

  1. (i)

$v_{3}v_{5}\in E(G)$. In this case $v_{1}v_{3}$ lies on the non-facial 3-cycle
$v_{1}v_{3}v_{6}v_{1}$. However, this leads to a contradiction, since the
6-hole is contained either in the 5-cycle $v_{5}v_{3}v_{6}v_{1}v_{2}v_{5}$ or
in the 5-cycle $v_{6}v_{3}v_{2}v_{5}v_{1}v_{6}$. Hence by symmetry neither of
the edges $v_{3}v_{5},v_{4}v_{5}$ is allowed.

  2. (ii)

$v_{3}v_{6},v_{4}v_{6}\in E(G)$. In this case, indicated in Figure 18, we may
assume that the hole is contained in the planar 6-cycle
$v_{1}v_{5}v_{2}v_{4}v_{6}v_{3}v_{1}$ and that the planar 6-cycle
$v_{1}v_{5}v_{2}v_{3}v_{6}v_{4}v_{1}$ is triangulated. This implies that
$v_{2}v_{3}$ is an $FF$ edge and so lies on non-facial 3-cycle. However, the
only candidate cycle is $v_{3}v_{2}v_{6}v_{3}$ and if $v_{2}v_{6}$ lies in
$E(G)$ then the hole is contained in the 5-cycle
$v_{1}v_{5}v_{2}v_{6}v_{3}v_{1}$, a contradiction.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{5}$$v_{6}$$v_{6}$ Figure 18. Edges
$v_{3}v_{6},v_{4}v_{6}$ in $G$ leads to a contradiction.

We have shown that no $FF$ edge is allowed. Suppose now that $G$ contains a
face, described by the vertices $v_{1},v_{2}$ and $v_{3}$. Since there are no
$FF$ edges, all edges $v_{1}v_{2},v_{2}v_{3}$ and $v_{1}v_{3}$ lie on the
boundary of the hole. Moreover, since they form a face of the graph, they
cannot form a 3-cycle path in the boundary of the hole. Only 3 edges of the
boundary cycle are left to be determined, so we may assume that the path
$v_{1}v_{2}v_{3}$ lies on the boundary. Therefore, without loss of generality,
there exists a vertex $v_{4}$ on the boundary that connects the two paths,
$v_{1}v_{2}v_{3}$and $v_{1}v_{3}$, so we obtain the 5-path
$v_{1}v_{3}v_{4}v_{1}v_{2}v_{3}$. But this implies that the remaining edge of
the 6-hole is $v_{1}v_{3}$, which would break the simplicity of the graph.
Hence the graph contains no faces and the proof is complete.

$v_{1}$$v_{2}$$v_{3}$ Figure 19. The uncontractible graph $G^{2}_{3}$.

∎

##  5\. The irreducibles

We show that an irreducible $(3,6)$-tight ${\mathcal{P}}$-graph is
uncontractible. Thus, if a graph $G$ in ${\mathfrak{P}}_{k}$, for $k=1,2$ or
$3$, has a contractible edge $e$ (so that $G/e$ is a simple graph) then there
exists a contractible edge $f$, which need not be the edge $e$, such that the
contracted graph is simple and satisfies the sparsity condition for membership
in ${\mathfrak{P}}_{k}$.

Recall that Lemma 3.5 identifies the obstacles to the preservation of
$(3,6)$-sparsity when contracting a contractible edge of
$G\in{\mathfrak{P}}_{k}$, namely that the edge lies on the boundary of a
subgraph of $G$ which is in ${\mathfrak{P}}_{l}$ for some $l\leq k$. For $k=1$
this boundary corresponds to a directed 6-cycle $c$ and we also refer to it in
subsequent proofs as a _critical 6-cycle_. Likewise for $k=2$ or $k=3$ the
edge $e$ lies on the boundary of one of the holes of a subgraph
$G\in{\mathfrak{P}}_{l}$ and we refer to the associated cycle as a _critical
5-cycle_ or _critical 4-cycle_.

######  Proposition 5.1.

Let $G\in{\mathfrak{P}}_{1}$ be irreducible. Then $G$ is uncontractible.

###### Proof.

Suppose that $G$ is irreducible with a contractible edge $e=xy$. By Lemma 3.5
there is a critical 6-cycle $c$, containing $e$, which is the boundary of a
subgraph $G_{1}\in{\mathfrak{P}}_{1}$. Since $c$ properly contains the hole of
$G$ this contradicts Lemma 4.2, completing the proof. ∎

######  Proposition 5.2.

Let $G$ be an irreducible graph in ${\mathfrak{P}}_{k}$, for $k=2$ or $3$.
Then $G$ is uncontractible.

###### Proof.

Suppose that $G$ is irreducible and $e$ is a contractible $FF$ edge in $G$. By
Lemma 3.5 there is a decomposition $G=G_{1}\cup A$ with $e\in\partial G_{1},$
and $G_{1}\in{\mathfrak{P}}_{l},$ for some $l\leq k$.

$e$$v$$v_{1}$$v_{2}$$w$$y$$x$$G_{1}$$v_{3}$$z$

Figure 20.  A ${\mathcal{P}}$-diagram for a critical 6-cycle for $e$.

_Case $k=2,l=1$._ Figure 20 illustrates the planar 6-cycle boundary $c$ of
$G_{1}$ and we assume it includes the contractible edge $e$ and that it
contains the planar 4- and 5-cycle boundaries of the two holes of $G$. Since
$G$ is simple $c$ has 6 distinct vertices.

For the first part of the proof we show that $G$ contains $vv_{1}$, perhaps
after relabelling $v_{1},v_{2}$, that $yvv_{1}v_{2}v_{3}y$ is the boundary of
the 5-cycle hole, and that $xvv_{1}wx$ is the boundary of the 4-cycle hole.

Note that $G_{1}$ is a contractible graph, for otherwise, by the previous
section, $G_{1}=G_{3}^{2}$, with 3 vertices. By Proposition 5.1 $G_{1}$ is
reducible and so there is an $FF$ edge edge $h$ with
$G_{1}/h\in{\mathfrak{P}}_{1}$. If $h$ lies on a critical 6-cycle $c^{\prime}$
in $G$ then it necessarily lies on a critical 6-cycle in $G_{1}$. This is
because the subpath of $c^{\prime}$ which is interior to $c$ must have the
same length as one of boundary paths of $c$ between the corresponding
vertices. (Otherwise the 6-cycle hole is contained in a planar cycle of length
at most 5.) Thus, since $G$ is irreducible, $h$ must lie on a nonfacial
3-cycle in $G$ with some edges that are internal to $c$. To avoid sparsity
violation there must be 2 such edges, say $h_{1},h_{2}$. Moreover, since $h$
is a contractible edge in $G_{1}$ the edges $h_{1},h_{2}$ form a diameter of
the 6-cycle $c$. This diameter together with subpaths of $c$, yields two
planar 5-cycles which contain the holes of $G$. Considering the 5-cycle hole,
Lemma 4.2 implies that, perhaps after relabelling, the pair $h_{1},h_{2}$ is
equal to the pair $yv,vv_{1}$ or to a pair $wu,uv_{3}$ for some vertex $u\neq
v$ interior $c$. In the first case $yvv_{1}v_{2}v_{3}y$ is the boundary of the
5-cycle hole and, by a further application of Lemma 4.2, $xvv_{1}wx$ is the
boundary of the 4-cycle hole. The second case cannot occur, since one of the
edges $xv,yv$ must be an $FF$ edge, and one can see that it does not lie on a
nonfacial 3-cycle or a critical 4-, 5- or 6-cycle.

For the next part of the proof we show that $G_{1}$ has no interior vertices.
Let $u$ be an interior vertex of $G_{1}$ and let $f$ be one of its incident
$FF$ edges. Then since $G$ is irreducible, by the hole inclusion lemma, Lemma
4.2, $f$ does not lie on a critical 6-cycle. Also if $f$ lies on a nonfacial
3-cycle then by Lemma 4.1 it lies on a nonplanar nonfacial 3-cycle. It follows
from the $(3,6)$-sparsity of $G$ that $\deg v\geq 6$ and so there are at least
3 distinct nonplanar nonfacial 3-cycle through $u$. However this implies that
every hole of $G$ is contained in a planar 4-cycle, a contradiction.

$e$$v$$v_{1}$$v_{2}$$w$$y$$x$$G_{1}$$v_{3}$$z$$H$$H$

Figure 21.  $G_{1}$ has no interior vertex and $z=v_{1}$.

Since $z$ is not an interior vertex of $G_{1}$ it is equal to $v_{1}$ (see
Figure 20). By Lemma 4.1(i) we have $\deg(v_{2})\geq 4$ and $\deg(v_{3})\geq
4$. Since $G_{1}$ is $(3,6)$-tight it follows that both vertices have degree 4
and that $G$ must have the structure indicated in Figure 21. In particular,
$v_{3}w$ does not lie on a nonfacial 3-cycle or a critical cycle and so
$G/v_{3}w$ is reducible, a contradiction.

_Case $k=2,l=2$._ We argue by contradiction and assume that $G$ is irreducible
and $e$ is a contractible $FF$ edge in $G$ which, by Lemma 3.5, lies on the
boundary of the proper subgraph $G_{1}\in{\mathfrak{P}}_{2}$. Each of the two
holes of $G_{1}$ must contain a hole of $G$, with the boundary cycles are of
the same length. By Lemma 4.2 this is a contradiction.

_Case $k=3,l=2$._ This case follows similarly. ∎

##  6\. Constructibility and 3-rigidity

Combining results of the previous sections we obtain the following
construction theorem and the proof of Theorem 1.1.

######  Theorem 6.1.

Let $G$ be a simple (3,6)-tight graph which is embeddable in the real
projective plane ${\mathcal{P}}$. Then $G$ is constructible by a finite
sequence of planar vertex splitting moves from at least one of the eight
${\mathcal{P}}$-graphs,
$G_{3}^{2},G_{4}^{3},G_{5}^{1},G_{6,\alpha}^{1},G_{6,\beta}^{1},G_{6,\alpha}^{2},G_{6,\beta}^{2},G_{7}^{0}$.

###### Proof.

As we have observed at the beginning of Section 4 it is evident that $G$ can
be reduced to an irreducible (3,6)-tight ${\mathcal{P}}$-graph, $H$ say, by a
sequence of planar edge contraction moves. By the results of Section 5 the
irreducible graph $H$ is uncontractible, and so, by the results of Section 4,
it is equal to one of the eight uncontractible ${\mathcal{P}}$-graphs. Since a
planar edge-contraction move is the inverse of a planar vertex splitting move
the proof is complete. ∎

###### Proof of Theorem 1.1.

Let $G$ be the graph of a partial triangulation of the real projective plane.
If $G$ is minimally 3-rigid then it is well-known that $G$ is necessarily
$(3,6)$-tight [11].

Suppose on the other hand that $G$ is $(3,6)$-tight. Then, by Theorem 6.1 the
graph $G$ is constructible by planar vertex splitting moves from one of the
eight uncontractible ${\mathcal{P}}$-graphs, each of which has fewer than $8$
vertices. It is well-known that all $(3,6)$-tight graphs with fewer than $8$
vertices are minimally 3-rigid. Since vertex splitting preserves minimal
3-rigidity (Whiteley [14]) it follows that $G$ is minimally 3-rigid. ∎

Acknowledgements. This research was supported by the EPSRC grant EP/P01108X/1
for the project _Infinite bond-node frameworks_ and by a visit to the Erwin
Schroedinger Institute in September 2018 in connection with the workshop on
_Rigidity and Flexibility of Geometric Structures_.

## References

  * [1] D. W. Barnette, Generating the triangulations of the projective plane, J. Comb. Theory33 (1982), 222-230.
  * [2] D. W. Barnette and A. Edelson, All orientable 2-manifolds have finitely many minimal triangulations, Israel. J. Math., 62 (1988), 90-98.
  * [3] D.W. Barnette, and A.L. Edelson, All 2-manifolds have finitely many minimal triangulations, Israel J. Math., 67 (1989), 123-128.
  * [4] A. Cauchy, Sur les polygones et polyèdres. Second Mémoir. J École Polytechn. 9 (1813) 87-99; Oeuvres. T. 1. Paris 1905, pp. 26-38.
  * [5] J. Cruickshank, D. Kitson and S.C. Power, The generic rigidity of triangulated spheres with blocks and holes, J. Combin. Theory Ser. B 122 (2017), 550-577.
  * [6] J. Cruickshank, D. Kitson and S.C. Power, The rigidity of a partially triangulated torus, Proc. London Math. Soc., 2018, https://doi.org/10.1112/plms.12215
  * [7] W. Finbow-Singh and W. Whiteley, Isostatic block and hole frameworks, SIAM J. Discrete Math. 27 (2013) 991-1020.
  * [8] W. Finbow-Singh, E. Ross and W. Whiteley, The rigidity of spherical frameworks: Swapping blocks and holes in spherical frameworks, SIAM J. Discrete Math. 26 (2012), 280-304.
  * [9] N. D. Gilbert and T. Porter, Knots and Surfaces, Oxford University Press, 1994.
  * [10] G. Grassegar, personal communication.
  * [11] J. Graver, B. Servatius and H. Servatius, Combinatorial rigidity, Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 1993.
  * [12] H. Gluck, Almost all simply connected closed surfaces are rigid, in Geometric Topology, Lecture Notes in Math., no. 438, Springer-Verlag, Berlin, 1975, pp. 225-239.
  * [13] T. Jordan and S. Tanigawa, Global rigidity of triangulations with braces, J. of Comb. Theory, Ser. B, 136 (2019), 249-288.
  * [14] W. Whiteley, Vertex splitting in isostatic frameworks, Structural Topology, 16 (1990), 23-30.