ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 153-183 https://doi.org/10.26493/1855-3974.1195.c71
(Also available at http://amc-journal.eu)
Generating polyhedral quadrangulations of the projective plane*
*
Yusuke Suzuki
Department of Mathematics, Niigata University, 8050 Ikarashi 2-no-cho, Nishi-ku, Niigata, 950-2181, Japan
Received 9 September 2016, accepted 7 June 2019, published online 17 September 2019
Abstract
We determine the 26 families of irreducible polyhedral quadrangulations of the projective plane under three reductions called a face-contraction, a 4-cycle removal and a 23 -path shrink, which were first given by Batagelj in 1989. Every polyhedral quadrangulation of the projective plane can be obtained from one of them by a sequence of the inverse operations of the reductions.
Keywords: Quadrangulation, projective plane, generating theorem. Math. Subj. Class.: 05C10
1 Introduction
A quadrangulation (resp., triangulation) of a closed surface is a simple graph cellularly embedded on the surface so that each face is quadrilateral (resp., triangular); in particular, a 2-path on the sphere is not a quadrangulation in this paper. It is known that every quadrangulation G of any closed surface is 2-connected and hence the minimum degree of G is at least 2. For quadrangulations of closed surfaces, we introduce typical three reductional operations called a face-contraction, a 4-cycle removal and a 23-path shrink, which were first given by Batagelj [2]. (See Figure 1. For a formal definition, see the next section.) In this paper, we call the above three operations P-reductions, while call the inverse operations P-expansions.
A quadrangulation of a closed surface is irreducible if no face-contraction is applicable without making a loop or multiple edges. In [20], it was proved that a 4-cycle is the unique irreducible quadrangulation of the sphere, and that there exist precisely two irreducible quadrangulations of the projective plane which are the unique quadrangular embeddings
»This work was supported by JSPS KAKENHI Grant Number 16K05250.
E-mail address: y-suzuki@math.sc.niigata-u.ac.jp (Yusuke Suzuki)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
154
Ars Math. Contemp. 17 (2019) 153-183
tVo

23-path shrink
face-contraction
4-cycle removal
Figure 1: P-reductions.
of K4 and K3j4 on the projective plane, respectively (see Figure 2). The irreducible quad-rangulations of the torus and the Klein bottle had also been determined in [15] and [14], respectively.
Figure 2: Irreducible quadrangulations of the projective plane where antipodal points of the hexagon and the octagon are identified respectively.
There are some results of quadrangulations of closed surfaces with some conditions. Batagelj [2] proved that any 3-connected quadrangulation on the sphere can be deformed into a cube by a sequence of V-reductions preserving 3-connectedness. However his proof contained a small mistake, and Brinkmann et al. [3] pointed out it and gave a corrected proof. Observe that a 3-connected quadrangulation of the sphere corresponds to a 4-regular 3-connected graph on the same surface by taking its dual. Broersma et al. [4] considered the same problem of the dual version with weaker conditions than Brinkmann et al. [3]. Nakamoto [17] discussed quadrangulations with minimum degree 3 and proved that any quadrangulation of the sphere (resp., the projective plane) with minimum degree 3 can be deformed into a pseudo double wheel (resp., a Mobius wheel or the unique quadrangular embedding of K3 4 on the projective plane) by a sequence of face-contractions and 4-cycle removals, preserving the minimum degree at least 3. Brinkmann et al. [3] also proved the same result only on the sphere using a restricted face-contraction. Furthermore, the results in [13] implies that every 3-connected quadrangulation of a closed surface F2 except the sphere can be reduced into one of irreducible quadrangulations of F2 by V-reductions, preserving the 3-connectedness. In addition, the recent study [25] discussed another reduc-tional operation defined for 3-connected quadrangulations of closed surfaces.
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	155
Let G be a graph embedded on a non-spherical closed surface F2. The representativity of G, denoted by r(G), is the minimum number of intersecting points of G and 7, where 7 ranges over all essential simple closed curves on the surface. A graph G embedded on F2 is r-representative if r(G) > r (see [22] for the details). A graph G embedded on a closed surface F2 is polyhedral if G is 3-connected and 3-representative. For example, each of two quadrangulations in Figure 2 is 3-connected but not polyhedral since these embeddings have representativity 2. Observe that all facial walks in a polyhedral embedded graph G are cycles, and any two of them are either disjoint, intersect in one vertex, or intersect in one edge. From such a point of view, polyhedral embedded graphs are frequently regarded as "good" embeddings in topological graph theory (see e.g., [8, 9, 10, 11]); note that every simple triangulation of a closed surface is polyhedral, while simple quadrangulations are not necessarily so. Furthermore, it is known that there is one to one correspondence between the set of polyhedral quadrangulations of a nonspherical closed surface F2 (resp.,
3-connected	quadrangulations of the sphere) and the set of optimal 1-embeddings of F2 (resp., optimal 1-planar graphs of the sphere, see [5, 6, 12, 21, 23, 24] for definitions and some results).
A face f = v0v1v2v3 of a polyhedral quadrangulation G of F2 is P-contractible (or simply contractible) if a face-contraction at either {v0, v2} or {vi, v3} results in another polyhedral quadrangulation of the same surface. Similarly, we define "P-removable (or simply removable)" and "P-shrinkable (or simply shrinkable)" for a 4-cycle C and a 2-path P, both of which are induced by vertices of degree 3, respectively. A polyhedral quadrangulation G of F2 is P-irreducible if G has none of a contractible face, a removable
4-cycle	and a shrinkable 2-path. The following is our main theorem in this paper. In the figures, to obtain the projective plane, identify antipodal pairs of points of each hexagon or octagon.
Theorem 1.1. There are precisely 26 families of P-irreducible quadrangulations of the projective plane presented in Figures 8, 11 and 16. Every polyhedral quadrangulation of the projective plane can be obtained from one ofthem by a sequence of P-expansions.
This paper is organized as follows. In the next section, we define basic terminology and reductional operations for quadrangulations. In Section 3, we show some lemmas to prove Theorem 1.1. In Section 4, we determine inner structures of 2-cell regions bounded by 4, 5 or 6-cycles of P-irreducible quadrangulations. Furthermore in Section 5, we consider ones bounded by several 6 or 8-walks. Before proving the main theorem, we classify P-irreducible quadrangulations with attached cubes into five types in Section 6. The last section is devoted to prove Theorem 1.1.
2 Basic definitions
We denote the vertex set and the edge set of a graph G by V (G) and E(G), respectively. A k-path (resp., k-cycle) in a graph G means a path (resp., cycle) of length k. (We define the length of a path (or cycle) by the number of its edges.) We say that S c V(G) is a cut of a connected graph G if G - S is disconnected. In particular, S is called a k-cut if S is a cut with |S| = k. A cycle C of G is separating if V(C) is a cut.
Let G be a graph 2-cell embedded on a closed surface F2. That is, each connected component of F2 - G is homeomorphic to an open 2-cell (or an open disc), which is called a face of G. We denote the face set of G by F (G). A facial cycle C of a face f is a cycle bounding f in G; i.e., C = df. Furthermore in our argument, we often discuss the interior
156
Ars Math. Contemp. 17 (2019) 153-183
of a 2-cell region D bounded by a closed walk W of G, i.e., W = dD, which contains some vertices and edges. (Note that a 2-cell region implies an "open" 2-cell region in this paper.) Then, D (resp., /) denotes a closure of D (resp., /), i.e., D = D U dD (resp., / = / U d/). Let fi,..., f denote the faces of G incident to v G V(G) where deg(v) = k. Then, the boundary walk of f U • • • U /k is the link walk of v and denoted by 1w(v). Clearly, 1w(v) bounds a 2-cell region containing a unique vertex v.
A simple closed curve 7 on a closed surface F2 is trivial if 7 bounds a 2-cell on F2, and 7 is essential otherwise. Furthermore, 7 is surface separating if F2 - 7 is disconnected. Clearly, a trivial closed curve on F2 is always separating, whereas an essential one is either separating or not. We apply these definitions to cycles of graphs embedded in the surface, regarding them as simple closed curves. It is an important property of the projective plane that any two essential simple closed curves are homotopic to each other.
Let G be a quadrangulation of a closed surface F2 and let / be a face of G bounded by a cycle v0viv2v3. (For brevity, we also use the notation like / = v0viv2v3.) The face-contraction of / at {v0, v2} in G is to identify v0 and v2, and replace the two pairs of multiple edges {v0vi,v2vi} and {v0v3,v2v3} with two single edges respectively. In the resulting graph, let [v0v2] denote the vertex arisen by the identification of v0 and v2. See the left-hand side of Figure 1. The inverse operation of a face-contraction is called a vertex-splitting. If the graph obtained from G by a face-contraction is not simple, then we do not apply it.
Let G be a quadrangulation of a closed surface F2, and let / be a face of G bounded by v0viv2v3. A 4-cycle addition to / is to put a 4-cycle C = m0m1m2m3 inside / in G and join vj and u for each i g {0,1,2,3}. The inverse operation of a 4-cycle addition is called a 4-cycle removal (of C), as shown in the center of Figure 1. We call the subgraph H isomorphic to a cube with eight vertices ui; v» for i G {0,1,2,3} an attached cube. We denote d(H) = v0v1v2v3, and we call C an attached 4-cycle of H.
As mentioned in the introduction, there exist some results of 3-connected quadrangu-lations (or quadrangulations with minimum degree 3) of closed surfaces; see [2, 3, 13, 17] for example. In those results, the 4-cycle removal is necessary by the following reason: Let G denote the resulting graph obtained from a 3-connected quadrangulation G of a closed surface by applying 4-cycle additions to all faces of G. Clearly G is 3-connected, however we cannot apply any face-contraction to G without making a vertex of degree 2.
In [3, 17], pseudo double wheels W2k (k > 3) and a Mobius wheels TW2fc-1 (k > 2) are treated as minimal quadrangulations of the sphere and the projective plane, respectively; for their formal definitions, see [17]. However, the following third reduction can reduce a pseudo double wheel W2k (k > 4)into W2(fc_1). That is, W2k can be deformed into a cube by k - 3 such reductions.
Assume that a polyhedral quadrangulation G of a closed surface F2 has a vertex u of degree 3. (Every 3-connected quadrangulation of either the sphere or the projective plane has such a vertex of degree 3, by Euler's formula.) Let v0v1 • • • v5 be a 6-cycle bounding a 2-cell region D on F2, which contains a unique vertex u and we assume that v1; v3 and v5 are neighbors of u. The 23-vertex splitting of u is the expansion of G, defined as follows:
(i)	Delete u and the three edges incident to u.
(ii)	Put a 2-path u0u1u2 into the interior of D and add edges u0v1, u0v3, u1v0, u2v3 and
u2v5.
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	157
Note that each of u0, u and u2 has degree 3 in the resulting graph. The inverse operation of a 23-vertex splitting is called a 23-path shrink, as shown in the right-hand side of Figure 1.
Similarly to the case of 4-cycle removals, it is not difficult to see that 23-path shrinks are necessary, when considering P-irreducible quadrangulations; replace an attached cube with a graph having a long path consisting of vertices of degree 3 under some conditions. Now, we have defined all the operations in the paper. Note that all of them preserve the bipartiteness of quadrangulations of closed surfaces.
3 Lemmas
To prove our main theorem, we show some lemmas which state properties of polyhedral (P-irreducible) quadrangulations of closed surfaces. We first give the following proposition which is however clear by the definition of polyhedral quadrangulations.
Proposition 3.1. A polyhedral quadrangulation has no vertex of degree 2.
The following holds not only for quadrangulations but also for even embeddings of closed surfaces F2, that is, a graph on F2 with each face bounded by a cycle of even length. Taking a dual of an even embedding and using the odd point theorem, it is easy to show the following.
Lemma 3.2. An even embedding of a closed surface has no separating closed walk of odd length.
The length of two cycles in an even embedding of a closed surface F2 have the same parity if they are homotopic to each other on F2 (see [1, 7, 16]). Furthermore, it is well-known that any two essential closed curves on the projective plane are homotopic to each other, and hence the following holds.
Lemma 3.3. The length of two essential cycles in an even embedding of the projective plane have the same parity.
When classifying P-irreducible quadrangulations in the latter half of the paper, we focus on whether such a quadrangulation is bipartite or non-bipartite.
Lemma 3.4. If a quadrangulation G of the projective plane admits an essential cycle of even (resp., odd) length, then G is bipartite (resp., non-bipartite).
Proof. If G admits an essential cycle of even length, then every essential cycle of G has even length by the previous lemma. Of course, all trivial cycles of G is separating and hence have even length by Lemma 3.2. Therefore, G is bipartite.	□
We denote the set of vertices of a graph G with degree i by Vi(G) (or simply Vi). In this paper, we often focus on the subgraph of G induced by V3, and denote it by (V3)G. In [17], the following lemma was proved.
Lemma 3.5. Let G be a quadrangulation of a closed surface F2 with minimum degree at least 3 and assume that (V3)G contains a cycle C of length k. Then k > 3 and one of the followings holds;
(i) if k = 4, then G is a cube on the sphere or C is an attached 4-cycle of an attached cube in G,
158
Ars Math. Contemp. 17 (2019) 153-183
(ii)	if k is odd, then G is a Mobius wheel Wk on the projective plane,
(iii)	if k is even and at least 6, then G is a pseudo double wheel Wk on the sphere.
Let G be a quadrangulation of a closed surface F2 and let f = v0viv2v3 be a face of G. Then a pair vi+2} is called a diagonal pair of f in G for each i e {0,1}. A closed curve 7 on F2 is a diagonal k-curve for G if 7 passes only through distinct k faces f0,..., fk-1 and distinct k vertices x0,..., xk-1 of G such that for each i, f and fi+1 share x4, and that for each i, {xi-1, x4} forms a diagonal pair of f of G, where the subscripts are taken modulo k. Furthermore, we call a simple closed curve 7 on F2 a semidiagonal k-curve if in the above definition {xi-1, x4} is not a diagonal pair for exactly one i; note that xi-1xi is an edge of df in this case.
Lemma 3.6. Let G be a quadrangulation of a closed surface F2 with a 2-cut {x, y}. Then there exists a surface separating diagonal 2-curve for G only through x and y.
Proof. Observe that every quadrangulation of any closed surface F2 is 2-connected and admits no such closed curve on F2 crossing G at most once. Thus there exists a surface separating simple closed curve 7 on F2 crossing only x and y, since {x, y} is a cut of G.
We shall show that 7 is a diagonal 2-curve. Suppose that 7 passes through two faces f1 and f2 meeting at two vertices x and y. If 7 is not a diagonal 2-curve, then x and y are adjacent on df1 or df2. Since G has no multiple edges between x and y, and since {x, y} is a 2-cut of G, we may suppose that x and y are adjacent in df1, but not in df2. Here we can take a separating 3-cycle of G along 7. This contradicts Lemma 3.2.	□
Lemma 3.7. Let G be a 3-connected quadrangulation of a closed surface F2, and let f = v0v1v2v3 be a face of G. If the face-contraction of f at {v0,v2} violates the 3-connectedness of the graph but preserves the simplicity, then G has a separating diagonal 3-curve passing through v0, v2 and another vertex x e V(G) — {v0, v1; v2, v3}.
Proof. Let G' be the quadrangulation of F2 obtained from G by the face-contraction of f at {v0,v2}. Since G' has connectivity 2, G' has a 2-cut. By Lemma 3.6, G' has a separating diagonal 2-curve 7' passing through two vertices of the 2-cut. Clearly, one of the two vertices must be [v0v2] of G', which is the image of v0 and v2 by the contraction of f; otherwise, G would not be 3-connected, a contradiction. Let x be another vertex of G' on 7' other than [v0v2]. Note that x is not a neighbor of [v0v2] in G'.
Now apply the vertex-splitting of [v0v2] to G' to recover G. Then a diagonal 3-curve for G passing through only v0, v2 and x arises from 7' for G'.	□
Lemma 3.8. Let G be a 3-representative quadrangulation of a non-spherical closed surface F2 and let f = v0v1v2v3 be a face of G. If the face-contraction of f at {v0, v2} yields another quadrangulation with representativity at most 2 but preserves the simplicity, then G has either an essential diagonal 3-curve or an essential semi-diagonal 3-curve, which passes through v0, v2 and another vertex x e V(G) — {v0, v1; v2, v3}.
Proof. Let G' be the quadrangulation of the non-spherical closed surface F2 obtained from G by a face-contraction of f at {v0, v2}. If the representativity of G' is at most 1, then G would have an essential simple closed curve crossing with G at most twice, contrary to G being 3-representative. Thus G' has representativity 2 and hence G' admits either an essential diagonal 2-curve or an essential semi-diagonal 2-curve. Similarly to Lemma 3.7,
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	159
one of the two vertices passed by the curve must be [v0v2] of G' and G has an essential
diagonal (resp., semi-diagonal) 3-curve when the former (resp., the latter) case happens.
□
The following lemmas show properties of P-irreducible quadrangulations of non-spherical closed surfaces. To simplify our statements, we suppose that G represents a P-irreducible quadrangulation of a non-spherical closed surface F2 hereafter in this section.
Lemma 3.9. If G has a 4-cycle C = v0viv2v3 bounding a 2-cell region D, then there is no face f of G in D such that one of the diagonal pairs of f is {v0, v2} or {v1; v3}.
Proof. Suppose, for a contradiction, that G has a 4-cycle C = v0v1v2v3 bounding a 2-cell region D and a face f bounded by av1cv3 in D. We assume that D contains as few vertices of G as possible. We denote the subgraph of G in D by H; note that H can be regarded as a quadrangulation of the sphere.
Since C is separating, we have df = C. Furthermore, G is P-irreducible and hence f is not P-contractible at {a, c}. If the face-contraction at {a, c} breaks the simplicity of the graph, then G has edges {ax, cx} for x G V(G) - {v1; v3}. (Clearly, it does not have a loop.) If x G V(G) - V(H), we would have df = C, contrary to our assumption. Thus, we may assume that x is either v0 or v2, now say v0; observe that v0 = a, c in this case. Now G would have an edge av0 (or cv0) and it contradicts Lemma 3.2.
By the above argument, the face-contraction at {a, c} does not break the simplicity, hence it breaks the 3-connectedness or the property of representativity at least 3. That is, we find either a surface separating diagonal 3-curve or an essential diagonal 3-curve (or an essential semi-diagonal 3-curve) passing through f and {a, c} by Lemmas 3.7 and 3.8. In each case, if {a, c} n {v0, v2} = 0, then f could not be passed by such a diagonal curve. Therefore we may suppose that a = v0 and c = v2.
By Lemma 3.2 again, there is not an edge joining c and v2. Thus, we can find a face f' of H one of whose diagonal pairs is {c, v2}. Let C be the 4-cycle v1v2v3c of G. Since deg(c) > 3, we have df' = C'. Therefore, C' and f' are a 4-cycle and a face which satisfy the assumption of the lemma, and moreover, C' can cut a strictly smaller graph than H from G. Thus, this contradicts the choice of C.	□
Lemma 3.10. Let f = v0v1v2v3 be a face of G. If the face-contraction of f at {v0, v2} breaks the simplicity of the graph, then there is a vertex x G V (G) — {v1; v3} adjacent to both of v0 and v2 such that v0v1v2x is an essential 4-cycle in G. In particular, if F2 is the projective plane, then G is bipartite.
Proof. First, assume that the face-contraction yields a loop. Then, we have v0v2 G E(G). By Lemma 3.2, v0v1v2 should be an essential 3-cycle. However, we would find an essential simple closed curve intersecting G at only v0 and v2, contrary to G being 3-representative.
Therefore, we may assume that the face-contraction yields multiple edges. Under the conditions, there should be a vertex x g V(G) — {v0, v1; v2, v3} which is adjacent to both of v0 and v2. If a 4-cycle v0v1v2x is trivial and bounds a 2-cell region D, then D and f would satisfy the conditions of Lemma 3.9, a contradiction. Therefore v0v1v2x should be essential. If F2 is the projective plane, then G is bipartite by Lemma 3.4.	□
Lemma 3.11. If G has a trivial diagonal 3-curve 7, then the disc bounded by 7 contains the unique vertex, which has degree 3.
160
Ars Math. Contemp. 17 (2019) 153-183
Proof. Suppose that 7 passes through three vertices {v0, v1; v2} and three faces {f0, /1, /2} where each f is bounded by viaivi+16i so that the 6-cycle v0b0v1b1v2b2 bounds a 2-cell region D including f and for i £ {0,1,2} (v3 = v0). Suppose, for a contradiction, that D contains at least two vertices. That is, this implies that a0, a1 and a2 could not be identified to one vertex. Thus, we can find a vertex a4 = ai+1, ai+2, now say a0 (a0 = a1, a2).
If there is an edge joining a0 and v2, then we can find a 2-cell region D' bounded by a0v2b2v0. Since a0 = a2, D' is not a face of G. Furthermore we have deg(a2) > 3 and hence the region bounded by a0v2a2v0 is not a face of G and includes at least one vertex. This means that D' satisfies the conditions of Lemma 3.9, a contradiction. Therefore, we conclude that a0v2 £ E(G).
Now consider the face-contraction of f0 at {a0,b0}. Since G is P-irreducible, G should have a diagonal 3-curve or a semi-diagonal 3-curve passing through three vertices {a0, b0, x} for x £ V(G) - {a0, b0}. (Note that the face-contraction clearly preserves the simplicity of the graph by the above argument, i.e., a0v2 £ E(G).) Since a0 is an inner vertex of D, x must be a vertex of dD.
However, since a0 = a1,a2, x must coincide with v2. Since a0v2 £ E(G) again, there should be a face whose diagonal pair is {a0, v2}, but it contradicts Lemma 3.2. Hence, we
can conclude that D contains exactly one vertex a0 (= a1 = a2) and the lemma follows.
□
Lemma 3.12. Let f = v0v1v2v3 be a face of G with deg(v0), deg(v2) > 4.
(i)	If F2 is the projective plane, then a face-contraction of f at {v1; v3} preserves the 3-connectedness.
(ii)	If F2 is not the projective plane and if a face-contraction of f at {v1; v3} breaks the 3-connectedness, then G has an essential separating diagonal 3-curve 7 passing through v1;v3 and another vertex x £ V(G) — {v0,v1,v2,v3}.
Proof. The statement (ii) immediately follows from Lemmas 3.7 and 3.11. In the projective-planar case, we cannot take such an essential separating diagonal 3-curve 7.	□
Lemma 3.13. The induced subgraph (V3)G has no vertex of degree 3.
Proof. Suppose, for a contradiction, that G has a vertex v with deg(v) = 3 and each of its three neighbors also has degree 3 (see the left-hand side of Figure 3). Note that the boundary of the hexagon is a cycle of G; otherwise, it would disturb the simplicity of G, Lemma 3.2, Lemma 3.9 or the property of representativity at least 3. We can easily find a trivial separating diagonal 3-curve passing through {v0, v1; v2} and that the 3-cut cuts off the four vertices, contrary to Lemma 3.11.	□
Suppose that the induced subgraph (V3)G of a P-irreducible quadrangulation G has a path P = u0u1u2 of length 2. Then the configuration around P becomes the center of Figure 3. The following lemma refers to the non-shrinkability of P.
Lemma 3.14. Let P = u0u1u2 be a 2-path in G induced by vertices of degree 3 (as shown in the center of Figure 3) and assume that deg(v4) > 4. Then, there is an essential diagonal 3-curve or an essential semi-diagonal 3-curve passing through {v0, u1; v2}.
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	161
Proof. Apply the 23-path shrink to P and denote G' be the resulting graph. Let u be a vertex of G' which is the shrunk image of P; note that u is adjacent to v0, v2 and v4. Since G is P-irreducible, G' is not a polyhedral quadrangulation. If G' is not simple, uv0 and uv2 must be multiple edges. This implies that v0 = v2, however this also implies that G is not simple or v1 has degree 2 in G, a contradiction.
Next, we assume that G' has a 2-cut. By Lemma 3.6, G' has a separating diagonal 2-curve 7' passing through {v0, v2}; otherwise, G would have a 2-cut. Now we can find a separating diagonal 3-curve 7 in G corresponding to 7' naturally. Note that 7 is not a semi-diagonal 3-curve by Lemma 3.2. Let f = v0xv2y be the third face passed by 7, which lies outside of the hexagon bounded by v0v1v2v3v4v5. If 7 is essential, then we are done. Therefore, we assume that 7 is trivial. If neither of x and y corresponds to v1, then we have got a contradiction by Lemma 3.9. Thus, one of x and y, say x, corresponds to v1. This means that deg(v1) = 3, however, it contradicts Lemma 3.13.
Finally, assume that G' has representativity at most 2. Similarly, G' has an essential diagonal 2-curve or an essential semi-diagonal 2-curve passing through {v0, v2}. We can easily find our required essential curve passing through {v0, u1; v2} of G.	□
Lemma 3.15. The induced subgraph (V3)g has no path of length at least 3.
Proof. Suppose to the contrary that G has such a path P = u0u1u2v2 (see the right-hand side of Figure 3). By the above lemma, z should coincide with v0. However, v1 z would become multiple edges, a contradiction.	□
Lemma 3.16. Assume that G has an attached cube H with d(H) = v0v1v2v3, an attached 4-cycle C = u0u1u2u3 and ujVj G E(G) for each i G {0,1,2,3}. Then there is an essential diagonal (or semi-diagonal) 3-curve 7passing through {v0, u1; v2} or {v1, u2, v3}.
Proof. Apply the 4-cycle removal of C to G and let G' denote the resulting graph. It is clear that the 4-cycle removal clearly preserves the simplicity of the graph. Thus, first suppose that G' is not 3-connected. By Lemma 3.6, we can find a separating diagonal 2-curve 7' in G' passing through {v0, v2} or {v1; v3}. If 7' is trivial, then it contradicts Lemma 3.9. If 7' is essential, we can find our requied diagonal 3-curve 7 in G.
Therefore, we may assume that G' has representativity at most 2 and has an essential diagonal (or semi-diagonal) k-curve 7' where k is at most 2. If 7' does not pass through a face f = v0v1v2v3, then G also has representativity at most 2, contrary to our assumption. Thus, 7' passes through f and two vertices {v0, v2} or {v1; v3} and we got our conclusion. (Note that 7' does not pass through two neighboring vertices of v0v1v2v3. Otherwise, 7' would be an essential semi-diagonal 2-curve also in G.)	□
162
Ars Math. Contemp. 17 (2019) 153-183
For an attached cube H with d(H) = v0viv2v3, we call a pair of two vertices {vj; vi+2} a cube diagonal pair of H for each i e {0,1}. In particular, a cube diagonal pair is facing if they are on a boundary cycle of a face f of G outside the 2-cell region bounded by d(H). According to the above argument, an essential diagonal (or semi-diagonal) 3-curve passes through f.
4 Regions bounded by 4-, 6- or 8-cycles
Consider a disk D bounded by a cycle C = v0v1 • • • v2m-1 of length 2m. Put a vertex x into the center of D and join it to v2i for each i e {0,..., m - 1}. Then, the resulting disk quadrangulation is a pseudo wheel and denoted by W2m.
Lemma 4.1. Let G be a quadrangulation of a closed surface F2 and let D be a 2-cell region bounded by a closed walk C of length 4, 6 or 8 such that
(i)	there is at least one vertex inside D,
(ii)	all vertices inside D have degree at least 3 and
(iii)	D does not have a unique vertex x of degree 4 such that lw(x) = C (when |C | = 8). Then, there exists a vertex of degree 3 inside D.
Proof. Let H be a graph contained in D. It suffices to prove the case when C is a cycle. (Even if C is not a cycle, i.e., there exists a vertex appearing twice on C, the analogous proof works.) We use induction on | V(H) |. Let v0,..., vm-1 be vertices lying on C in this order for some m e {4, 6, 8}. The initial step of the induction is the case that | V(H) | = 7. In this case, H must be isomorphic to W- and its center vertex has degree 3. (When the length of C equals 4, it is not difficult to list up all the (disc) quadrangulations with at most 7 vertices, e.g., see [19]. Every such graph has a vertex of degree 2 not lying on any specified outer cycle.) Thus, we suppose that |V(H)| > 8 in the following argument.
First, assume that there is a diagonal of C. Since at least one of the two regions separated by the diagonal satisfies Conditions (i) - (iii), there is a vertex of degree 3 inside the region by the induction hypothesis. Thus, we suppose that there is no diagonal in D.
Furthermore, suppose that there is a vertex x joining two vertices v» and vi+2. Then, the 2-path vjxvi+2 separates D into a quadrilateral region D' and the other region D". If D' contains a vertex, then the induction hypothesis works immediately. Thus, we may assume that D' contains no vertex. Further, if D'' contains at least one vertex and G n D" is not isomorphic to W8-, then we can also apply the induction hypothesis. When the case that G n D" is isomorphic to W8-, the unique inner vertex y of D'' should be adjacent to x, and hence x has degree 3; otherwise, the degree of x would become 2.
Therefore, we suppose that D'' contains no vertex. Under the condition, there should be edges joining x and alternate vertices on C so that H becomes disc quadrangulation since C has no diagonal. Then, H is isomorphic to W— since |V(H)| > 8. However, it contradicts (iii).
By the above arguments, we may assume that D contains no diagonal and no 2-path joining vj and vi+2. This implies that all vertices v» of C have degree at least 3. When |C| is equal to 6 or 8, add an extra vertex x outside D and join it to alternate vertices to obtain a quadrangulation H of the sphere; if |C| = 4, then we do nothing and let ii = H. Observe that H has minimum degree at least 3.
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	163
By Euler's formula, we have |V3(li)| > 8. Even if |C| = 8, the number of vertices of degree 3 on C is at most 4 by our construction of HH. Therefore, the lemma follows. □
The following lemma is important to determine the inner structures of 2-cell regions of P-irreducible quadrangulations bounded by closed walks of length 4, 6 or 8.
Lemma 4.2. Let G be a P-irreducible quadrangulation of a non-spherical closed surface and let D be a 2-cell region bounded by a closed walk W = w0w1 ■ ■ ■ wk-1 for some k G {4,6, 8}. Suppose that W does not bound a face of G and that G n D is not isomorphic to an attached cube. Then G n D includes;
(i)	a diagonal edge (when k G {6,8}),
(ii)	a 2-path wixwi+2,
(iii)	a 2-path wixwi+4 (when k = 8 and Wi = wi+4),
(iv)	a 3-path (or a 3-cycle if wi = wi+3) wixywi+3 (when k G {6, 8}) or
(v)	a 4-cycle wixyzwi+4 (when k = 8 and wi = wi+4),
where x, y and z are distinct inner vertices of D and the indices are taken modulo k.
Proof. In this proof, we call a path (or a cycle) in the statement a short path of D. Suppose, for a contradiction, that D includes no short path. By Lemma 4.1, D contains a vertex of degree 3 as an inner vertex; since if D has a unique vertex, then it clearly includes a short path of type (ii). First, assume that D contains a vertex ui of degree 3 of an attached cube Q; where Q consists of a 4-cycle C = u0uiu2u3 induced by vertices of degree 3 and d(Q) = v0v1v2v3 with an edge uivi for each i G {0,1,2,3}. We consider the cases depending on the order of V(C) n V(W).
Case I. |V(C) n V(W)| = 1 (assume w0 = u0): Then u0 would have a vertex of degree at least 4, contrary to the assumption.
Case II. |V(C) n V(W)| = 2: If such vertices are diagonal vertices of C, say u0 and u2, then we have deg(u0) > 4, as well as the above case. Thus, we suppose that such two vertices are adjacent on both of C and W, say w0 = u0 and w1 = u1. Note that u2 and u3 are inner vertices in this case. Since deg(w0) = deg(w1) = 3, v0 (resp., v1) should coincide with wk-1 (resp., w2). In this case, v2 and v3 are inner vertices of D; otherwise D would contain a short path (ii) or (iii). However, w2v2v3wk-1 would become (iv) if k G {6,8}; note that if k = 4, then wk-1w2 would form multiple edges since deg(wo) = deg(w1) = 3.
Case III. |V(C) n V(W)| = 3: We can easily exclude this case, since the unique inner vertex of C is adjacent to two vertices of W and it would form either (ii) or (iii).
Case IV. V(C) n V(W) = 0: By Lemma 3.16, at least one of cube diagonal pairs, say {v0, v2}, should be facing. We further divide this case into the following subcases.
Case IV-a. W is a cycle of G: Then both of v0 and v2 should be vertices of W. Note that by Lemma 3.2, {v0, v2} coincides with {wi; wi+2} or {wi; wi+4}. If one of v1 and v3 is an inner vertex of D, then D clearly would contain a 2-path of (ii) or (iii) in the lemma. Therefore, they also should be vertices of W. However, if k equals 6 or 8, then D would
164
Ars Math. Contemp. 17 (2019) 153-183
have a diagonal edge (i), on the other hand, if k = 4, then it corresponds to an attached cube, contrary to our assumption.
Case IV-b. W is not a cycle: Note that we only have to consider the case of k G {6,8}. This case is further divided into the following subcases.
Case IV-b-1. w = wi+3 (say w0 = w3): Note that G is nonbipartite since it includes an essential cycle of odd length. Now we may suppose that an essential simple closed curve of Lemma 3.16 passes through such a vertex w0 = w3. We may suppose that v0 = w0 in this case and there should be the edge v2w3 (see (a) in Figure 4). In the figure, we find a hexagonal region bounded by W' = w0wiw2w3v2vi. If there is no identification of vertices of W', then we would have a short path w0v1v2w3 of type (iv). Even if there is such an identification, we find either a short path (i) or (ii), a contradiction.
Case IV-b-2. w = wi+4 (assume w0 = w4): Similarly to the above arguments, we assume that v0 = w0 and there is a face bounded by v2sw4t in G where s, t G V(G). If there is no identification of vertices of closed walk W'' = w0w1w2w3w4sv2v1 bounding an octagonal region, there would be a short path of type (v). When there is identification of vertices of W'', we pay attention to the simplicity and the representativity of the whole graph; e.g., if v1 = s, we would have multiple edges w0 v1. In any case, we find our required short path.
(a)	(b)	(c)	(d)
Figure 4: Inside of a region bounded by closed walks of length 4, 6 or 8.
Therefore after this, we may assume that D does not contain a vertex of a 4-cycle induced by vertices of degree 3, that is, each inner vertex of degree 3 is on the path of (V3)G with length at most 2, by Lemmas 3.5, 3.13 and 3.15; note that a Mobius wheel in Lemma 3.5 is not polyhedral. We can take an inner vertex x of degree 3 so as to be an endpoint of a path of (V3)G; otherwise, each path of (V3)G would join two vertices of W, contrary to our assumption and Lemmas 3.2 and 3.15.
Let 1w(x) = v0v1v2v3v4v5 be the link walk of x and assume that v0, v2 and v4 are adjacent to x and that deg(v0), deg(v2) > 4. Now we apply the face-contraction of xv0v1v2 at {x, v1}, and denote the resulting graph by G'.
We first assume that G' is not simple. By Lemma 3.10, there is an edge joining v1 and v4 in G such that a cycle v1 v2xv4 of G is essential. Suppose that the edge v1v4 is in D. Clearly, W is not a cycle, and we may assume that k = 8 and that w0 = w4 = v4. However, it easily follows that there exists a short path passing through x. Also in the case that v1v4 runs outside of D, v1 and v4 should be vertices of W and hence we can find a
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	165
short path. Then, assume that G is simple in the following argument.
Next, we assume that either the representativity or connectivity of G is at most 2. In each case, G has an essential diagonal (or semi-diagonal) 3-curve 7 passing through x and v1 by Lemmas 3.8 and 3.12. In fact, there are some cases depending on the positions and identifications of vertices in D. However, in each case, the similar argument holds and hence we prove only one substantial case below, for the sake of brevity.
Here, we consider the case that 7 passes through {v1, x, v3} and that v1 = w1 and v3 = w3 (see (b) in Figure 4). In this case, if v2 = w2, D would contain a 2-path w1v2w3 of type (ii) in the lemma. Therefore we suppose v2 = w2. Note that each of v0, v4 and v5 is an inner vertex of D and that there is no edge v;w for l G {0,4, 5} and w G V(W); otherwise, there would be a short path.
Next, we assume deg(v4) > 4 and consider the face-contraction of v0xv4v5 at {v5, x}. By the above argument, v5 has no adjacent vertex of W and hence we do not have to care about the simplicity of the resulting graph. Thus, similarly to the above argument, we can find a face v5yw5z in D by Lemmas 3.8 and 3.12, where either w1 = w5 or w2 = w5, i.e., W is not a cycle of G. We assume w1 = w5 here. (The case when w2 = w5 can be shown in a similar way.) See (c) in Figure 4. Actually, k = 4 in this case. Note that y and z are inner vertices of D and further note that {y, z} n {v0, v4} = 0 by the above argument. It also implies that deg(v5) > 4 and deg(w5) > 4.
By Lemmas 3.8 and 3.12 again and by Lemma 3.2, there should be diagonal 3-curve 7" passing z, y and w G V(W); note that semi-diagonal 3-curve is not suitable since each of y and z is not adjacent to a vertex of V(W). In this case, we have k = 8 and w = w0 = w4 since if w = w4 = w6, w4w5 and w5w6 become multiple edges. However in this case, we find a short path (iv) of length 3 linking w0 and w5 (or a short path (iii) of length 2 linking w5 and w7).
Therefore, suppose that deg(v4) = 3 and there is a face w3v4v5p where p is an inner vertex of D; otherwise we would find a short path. Observe that deg(w3) > 4 in this case. Furthermore, if deg(v5) > 4, then we consider the face-contraction of w3v4v5p at {p, v4}. Similarly to the above argument, there must be a face psw6t where w2 = w6 since x and v0 are inner vertices of D and hence there is an essential diagonal 3-curve passing through {w2, v4,p}. However, we find a short 3-path w3psw6 in this case.
Hence, we may assume that deg(v5) = 3 and there is a face v0v5pq (see (d) in Figure 4). Then there is a 2-path xv4v5 induced by vertices of degree 3. By Lemma 3.14, there should be an essential diagonal (or semi-diagonal) 3-curve passing through {w2, v4,p}. Similarly, we can find a short path around it. (For example, if w2 = w5 and the edge pw5 g E(G) exists, then we find a short path w3pw5 of type (ii).) Thus, the lemma follows.	□
Figure 5 shows some partial structures of polyhedral quadrangulations of closed surfaces, each of which is bounded by a trivial 4-cycle v0v1v2v3. The center graph in the figure has a 4-cycle u0m1m2m3 induced by vertices of degree 3 and hence this partial structure is an attached cube. Recall that if a polyhedral quadrangulation is V-irreducible and has an attached cube, then one of two cube diagonal pairs is facing by Lemma 3.16. Next, see the right-hand side of Figure 5. For a natural number n, represents the graph having the following structure: There are n + 1 internally vertex-disjoint paths of length 2 between v0 and v2, including v0 v1v2 and v0v3v2, so that they divide the region bounded by v0v1v2v3 into n quadrilateral regions each of which has the structure Q2 having a facing cube diagonal pair {v0, v2}. Note that q21) corresponds to Q2.
166
Ars Math. Contemp. 17 (2019) 153-183
vq
v3,
N	y	
	Uq Ul	
	U3 U2	
N		
Vl
V2
Vq(
V3I
Vl
V2
Qi
Q 2
q23)
Figure 5: Inside a quadrilateral region.
Lemma 4.3. Let C = voviv2v3 be a cycle of length 4 bounding a 2-cell region D in a P-irreducible quadrangulation G of a non-spherical closed surface. Then, the interior of D has one of the structures Q1 and Q2n) (n > 1), as shown in Figure 5.
Proof. Use induction on the number of faces in D, say F > 1. If F = 1, then it is clear that D corresponds to a face of G and it has the structure Q1. Hence we suppose that F > 2 below.
If G n D is not an attached cube Q2, then there is a vertex x which is adjacent to both v0 and v2 (or v1 and v3) by Lemma 4.2. By the inductive hypothesis and Lemma 3.9, two
quadrilateral regions bounded by v0v1v2x and v2v3v0x are filled with Q^ and Q2m) for
(n)
n, m > 1. As a result, we obtain Q2 with n = l + m and the induction is completed. □
Note that replacing Q2 with Q2n) having the same facing cube diagonal pair preserves the property being a P-irreducible quadrangulation for any n > 2. Hence, there exist infinitely many P-irreducible quadrangulations of a non-spherical closed surface F2 if F2 admits one with an attached cube. To avoid the complexity in figures, we use simply Q2 to represent any Q2n) after this.
In the following lemmas, we discuss inside structures of regions bounded by 6- and 8-cycles. For brevity, we shall omit routines in the proofs.
Lemma 4.4. Let C = v0v1v2v3v4v5 be a trivial cycle of length 6 bounding a 2-cell region D in a P-irreducible quadrangulation G of a non-spherical closed surface. Then, the interior of D has one of the structures H1; H2,..., H17, as shown in Figure 6.
Proof. As well as the previous lemma, we use induction on the number of faces in D, say F > 2. If F = 2, then D has the structure H1. Hence we suppose that F > 3. Observe that the existence of a short path of (i), (ii) or (iv) is guaranteed by Lemma 4.2. We fill the divided regions with pieces as follows.
If C has a diagonal, then we apply Lemma 4.3 and obtain H1, H6 and H10 in Figure 6. Further, if there is an inner vertex x which is adjacent to both v0 and v2, then the quadri-
(n)
lateral region bounded by xv0v1v2 is filled with Q1 or Q2 (n > 1), and the hexagonal region bounded by v0xv2 v3 v4 v5 is filled with H for some i e {1,..., 17} by the inductive hypothesis. Checking the whole cases is a routine, so we omit it, however, most cases are excluded by lemmas in Section 3.
Furthermore, assume that D contains two inner vertices x and y such that 3-path v0xyv3 runs across D. Also in this case, we apply the inductive hypothesis to two separated hexagonal regions and obtain Hj's in Figure 6.	□
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane
167
H
H14	H15	H16
Figure 6: Inside a hexagonal region.
H1
Lemma 4.5. Let C = v0viv2 v3v4v5v6v7 be a trivial cycle of length 8 bounding a 2-cell region D in a P-irreducible quadrangulation G of a non-spherical closed surface. If D has no diagonal edge and no attached cube, then the interior of D has one of the structures Oi, O2,..., O8, as shown in Figure 7.
O 6
Or
Figure 7: Inside an octagonal region.
Proof. In this proof, all subscripts of vertices are taken modulo 8. We also use induction on the number of faces in D, say F. If F is at most 3, then D has a diagonal, contrary to the assumption of the lemma. If F = 4, then D includes a single vertex by Euler's formula and it should be adjacent to vi; vi+2, vi+4 and vi+6; for otherwise, D would contain a diagonal. This is clearly Oi in Figure 7. Therefore, we assume F > 5 hereafter. Observe that D contains a short path of type (ii), (iii) or (iv) by Lemma 4.2.
168
Ars Math. Contemp. 17 (2019) 153-183
First, we assume that D includes an inner vertex x which is adjacent to both v0 and v4. Then there are two hexagonal regions D' and D" bounded by xv0viv2v3v4 and xv4v5v6v0 respectively. Note that each of D' and D'' contains no attached cube. Then by the previous lemma, we fill them with H1; H2, H3, H4 and H5 in Figure 6 so that the whole configuration satisfies the condition of this lemma. By considering lemmas in Section 3, most cases are excluded and we obtain O1; O2, O3,04,05, O6 and O8 in Figure 7. Therefore, after this, we suppose that D contains no such vertex.
Secondly we assume that there is an inner vertex x in D which is adjacent to both v0 and v2. Then, there are a quadrilateral region D' and an octagonal region D'' divided by the 2-path v0xv2. By the assumption and Lemma 4.3, D' bounds a face of G. If D'' contains a diagonal edge, then it should be xv4 or xv6 by Lemma 3.2. However, in each case, there would be a forbidden 2-path; e.g., v0xv4 if the diagonal xv4 exists. Hence, we may assume that D'' contains no diagonal. Now we apply the inductive hypothesis and fill D'' with O1;..., O8 in Figure 7; note that most cases would contain a contractible face or a shrinkable 2-path by lemmas in Section 3. As a result, we obtain O1;..., O8. Then we also assume that D does not include such a 2-path.
Finally, we assume that D has a short path of type (iv) in Lemma 4.2. Actually, this 3-path divides D into a hexagonal region and an octagonal one. As well as the above case, we use the inductive hypothesis and Lemma 4.4, and obtain our conclusion.	□
Lemma 4.6. Let G be a P-irreducible quadrangulation of the projective plane. If G has a hexagonal 2-cell region D such that G n D is isomorphic to either H13 or H15 in Lemma 4.4, then G is one of J1; I2 and I3 shown in Figure 8.
Proof. Let C = v0v1 v2 v3v4v5 be a 6-cycle bounding a hexagonal region D such that GnD is isomorphic to either H13 or H15. We may assume that each of v0v1v2x and v3v4v5y bounds Q2 where x and y are distinct inner vertices of D. Now, cube diagonal pairs {v0, v2} and {v3, v5} are facing and there are such faces f1 = v0pv2q and f2 = v3sv5t outside of D by Lemma 3.16, wherep, q, s, t G V(G).
However, if f1 = f2, the two essential diagonal (or semi-diagonal) curves in Lemma 3.16 do not exist together on the projective plane. Therefore, we have f1 = f2, that is, v0v3, v2v5 G E(G) and f1 = f2 is bounded by v0v3v2v5. Under the conditions, the 6-cycle v0xv2v5yv3 bounds a 2-cell region and it should be filled with either H13 or H15 by Lemma 4.4. Actually we have three ways to take a pair {Hj, Hj} for i, j G {13,15} and the lemma follows; for example, if we fill those hexagonal regions with two H13's then we obtain I1.	□
5 Regions bounded by 6- or 8-walks
A boundary walk of a hexagonal region of a P-irreducible quadrangulation is not always a cycle, and the same vertex often appears twice along it. Such a hexagonal region can contain the following structure that generates an infinite series of P-irreducible quadran-gulations of a non-spherical closed surface.
Let h1 , h2 and h3 be three pieces with two terminals x1 and x2 shown in the first three configurations of Figure 9, and let [s1;..., sm] be a given sequence of 1, 2 and 3 of any length such that each of 2 and 3 does not continue; i.e., we do not permit a sequence like [..., 2,2,...]. Put hSl to hSm in a hexagon a161ca262d so that each x» coincides with a» for i G {1,2}, and identify paths between x1 and x2 in each neighboring pair
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	169
170
Ars Math. Contemp. 17 (2019) 153-183
of pieces. (See the rightmost configuration of Figure 9.) We denote the resulting graph by His[si,..., sm]; note that we implicitly exclude His[2] and His[3] since they cannot fill the hexagonal region solely. If His[si,..., sm] is contained in a P-irreducible quadrangulation G so that ai = a2, then each attached cube is not removable and each face is not contractible in this configuration; note that G is nonbipartite. We often denote His [si, ...,sm ] simply by His.
Xi
X2 hi
a 2
His [1, 2, 3]
Figure 9: Inside a hexagonal region including an infinite series His.
b
i
c
Figure 10: Inside a hexagonal region bounded by a closed walk (1).
See H19 in Figure 10. Note that the hexagonal region is bounded by a closed walk W = a1bca2de where a1 = a2 (= a) and the other four vertices b, c, d and e are distinct. Actually, H19 is appeared as a partial structure in P-irreducible quadrangulations of the projective plane. (In Lemma 5.3, it will be mentioned.) However, the following lemma can exclude H19 from the later arguments.
In the following three lemmas (Lemmas 5.1, 5.2 and 5.3), we let D be a hexagonal region bounded by a closed walk W = a1bca2de in a P-irreducible quadrangulation G of the projective plane where a1 = a2 (= a) and the other four vertices b, c, d and e are distinct.
Lemma 5.1. If G n D = H19, then G is isomorphic to in Figure 11.
Proof. Note that G is nonbipartite since G contains an essential cycle of length 3. Therefore, G has an edge be outside of D by Lemma 3.16. Then there are two quadrilateral regions bounded by abed and aebc. By Lemma 4.3, each of these regions is filled with either Q1 or Q2. However, if Q1 is used, that is, it corresponds to a face of G, then we can
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	171
easily find an essential simple closed curve intersecting G at only two vertices, a contradiction. Hence, we fill each of those regions with Q2 and obtain I20 in Figure 11. □
Lemma 5.2. G n D cannot be isomorphic to H_1 in Figure 10.
Proof. Similarly to Lemma 5.1, G has an edge cd in this case by Lemma 3.14, and both of two quadrilateral regions outside of D are filled with Q2 (see the right-hand side of Figure 10). However in this case, we would find a contractible face at {e, b} by Lemmas 3.8 and 3.12. Therefore the lemma follows.	□
Lemma 5.3. G n D is isomorphic to either H18 or H19.
Proof. We use induction on the number of faces in D, say F. If F is at most 3, then D includes at most one inner vertex by Euler's formula. In this case, although d(D) is not a cycle, G n D forms a structure like either H1 or H2 in Figure 6; we have to identify the top and the bottom vertices of H for i € {1,2}. However, G would have representativity at most 2, a contradiction. (Such an essential simple closed curve passes through a.) If F = 4, D includes exactly two vertices and we have G n D = H18[1]. Therefore, we assume that F > 5 after this. Similarly to the former lemmas, we discuss inner structures of divided regions by a short path; we have to consider (i), (ii) and (iv) in Lemma 4.2.
First, we assume that D contains a diagonal edge. By Lemma 3.2 and the simplicity of G, it should be ce or bd, now say ce, up to symmetry. Then each of two quadrilateral regions bounded by a1bce and da2ce should be filled with Q2; otherwise at least one of those regions forms a face of G, but we can easily find an essential simple closed curve passing through only two vertices of G. Therefore, we obtain H18[3,2] from this case. Then, we assume that D contains no diagonal hereafter.
Secondly, we assume that D includes an inner vertex x which is adjacent to a1 and c. Then the quadrilateral region D' bounded by a1bcx is filled with either Q1 or Q2. If we have the former, that is, a1bcx bounds a face of G, then we would find an essential simple closed curve intersecting G only at a and c, contrary to the assumption. Therefore, we assume the latter case. In this case, the hexagonal region D'' bounded by a 6-walk a1xca2de satisfies the assumption of this lemma. Thus, we use the inductive hypothesis and fill the region with either H18 or H19. If we use H19, then the configuration becomes a part of I20 by Lemma 5.1. However, this is not the case since b corresponds to d. Hence we fill D'' with H18 and obtain our desired conclusion. Then after this, we assume that there is no such inner vertex like x. (We also exclude similar paths a1xd, a2xb and a2xe.)
172
Ars Math. Contemp. 17 (2019) 153-183
Thirdly, we assume that there is an inner vertex x which is adjacent to b and e (or c and d). Then, there are a quadrilateral region bounded by a1bxe and a hexagonal region bounded by a 6-cycle bca2dex. We fill these regions by using the results of Lemmas 4.3 and 4.4 respectively. Most cases are excluded by lemmas in Section 3, but we obtain His[1], Hi8[3,2, 3] and Hw by filling them with {Qi,H2}, {Q2, Hw} and {Q2,H2}, respectively. (For reference, when we use {Q1, H4}, we obtain H-1 in Figure 10, but it had already been excluded by Lemma 5.2.)
Next, we consider the existence of an essential 3-cycle a1xya2 where x and y are inner vertices of D. In this case, we can apply the inductive hypothesis and fill two hexagonal regions with H18's and obtain our conclusion; we do not have to consider H19 by Lemma 5.1.
Finally we assume that there is a 3-path bxyd (or cxye) where both x and y are inner vertices of D. Then the boundary of each hexagonal region divided by the 3-path is a cycle, and we fill them by using Lemma 4.4. We only have to check H for i e {3,4,5}, since the existence of an attached cube, a diagonal edge and a single vertex of degree 3 clearly yields a short path discussed above. However, there is no pair to satisfy the conditions from this case. Hence, the induction is completed.	□
In the following lemma, we discuss a hexagonal region bounded by a 6-walk in which two vertices each appear twice.
Lemma 5.4. Let D be a hexagonal region bounded by a closed walk W = a1b1ca2b2d in a P-irreducible quadrangulation G of the projective plane with a1 = a2 (= a) and b1 = b2 (= b). Then G n D is isomorphic to one of H18, H20 and H21.
Proof. Since almost the same argument of the previous proof holds, we omit the proof of this lemma. However, we should pay attention to the following points:
(1)	When assuming that there is a 3-path cxyd where x and y are inner vertices of D, we obtain H20 in Figure 12; note that such a configuration was excluded in the previous lemma, since at least one of shaded faces in the right-hand side of Figure 12 is contractible by Lemma 3.8.
(2)	If there is an essential 3-cycle a1xya2 (or b1xyb2), then we apply Lemma 5.3 to each of two hexagonal regions divided by the cycle.
(3)	Using Q2 and H19, we can construct H21 in Figure 12.	□
Figure 12: Inside a hexagonal region bounded by a closed walk (2).
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane
173
c
Og(2)
Og(5)
010
Figure 13: Octagonal structure generating infinite series.
See the graph denoted by O9 (2) shown in the left-hand side of Figure 13. Observe that the octagonal region D is bounded by a closed walk W = aibcda2piq2p2 where ai = a2 (= a) and the other vertices are distinct. Now add two vertices p3 and q3 so that q2pia2p3 and p2q2p3q3 are quadrilateral faces. The resulting graph is denoted by O9(3). We inductively define the general form O9(m) from O9(m - 1) by adding two vertices pm and qm so that qm-ipm-2a2pm andpm-iqm-ipmqm (resp., aipm-2qm-ipm andpmqm-ipm-iqm) are quadrilateral faces if m is odd (resp., even); note that we define O9(m) for m > 2. This O9(m) satisfies the followings:
(a)	deg(qj) = 3 for each i e {0,...,m - 1}, while deg(pj) = 4 for each i e {1,...,m - 2} if m > 3.
(b)	If m is odd, then degD(b) = 2, degD(c) = 0, degD(d) = 1, degD(pm) = 1, degD(qm) = 0 and degD(pm-i) = 2.
(c)	If m is even, then degD(b) = 2, degD(c) = 0, degD(d) = 1, degD(pm-i) = 2, degD(qm) = 0 and degD(pm) = 1.
Lemma 5.5. Let D be an octagonal region bounded by a closed walk W = aibcda2efg in a P-irreducible quadrangulation G of the projective plane such that ai = a2 (= a) and the other vertices are distinct. Suppose the following conditions hold:
(a) Each of degD (b), degD (d), degD (e) and degD (g) is at least 1.
(ft) No two vertices of degree 3 in D are adjacent.
Then G n D is isomorphic to either O9(m) or Oi0 in Figure 13.
Proof. First of all, we show that D contains no diagonal edge. Suppose to the contrary that there is a diagonal edge in D, say bf; note that a diagonal edge like aid is immediately excluded since it yields multiple edges. Then, there is a quadrilateral region D' bounded by a 4-cycle aibfg. By Lemma 4.3 and the condition (ft) in the lemma, D' should be filled with Qi, that is D' corresponds to a face of G. However, it contradicts (a) in the lemma. Therefore, we conclude that D has no diagonal.
Now, we use induction on the number of faces in D, say F as well as previous lemmas. If F is at most 4, then D includes at most one inner vertex x by Euler's formula. Since D has no diagonal, G n D is a graph obtained from Oi in Figure 7 by identifying a pair of
174
Ars Math. Contemp. 17 (2019) 153-183
antipodal vertices. However in this case, we would find an essential simple closed curve intersecting G at only {a, x}, a contradiction. By careful observation, we have the unique configuration O9(2) with F = 5 faces in D; D includes exactly two inner vertices of degree 3. Therefore, the first step of the induction holds.
Similarly to the former lemmas, we divide the following argument along Lemma 4.2; other than (i) which is already excluded. Note that we shall implicitly exclude a short path already discussed in the former arguments.
Case I. There exists a short 2-path (ii) or (iii): First, such a vertex x adjacent to a1 and c violates condition (a) in the lemma, since D does not contain an attached cube by (3). (We also exclude such 2-paths a1x/, a2xc and a2x/.) Therefore, we assume that there is such a vertex x adjacent to b and d. Then the 2-path bxd divides D into an octagonal region D' and a quadrilateral region D"; note that D" corresponds to a face of G. If degD, (b), degD, (d) > 1, then we can apply the inductive hypothesis. However, if we use O9(m), then x would become degree 2. On the other hand, if we fill D' with O10, then the face-contraction of bcdx at {c, x} can be applied by Lemma 3.8. If degD, (b) = 0 and degD (d) = 0, then we can easily find an essential simple closed curve intersecting G at only a and x; we can take such a curve along a1bxda2.
Therefore, we assume that one of degD, (b) and degD, (d) is equal to 0 and the other is at least 1. We may assume that degD, (b) = 0 and degD, (d) > 1 without loss of generality. Under the condition, there is a face of G in D' bounded by a1bxy for y G V(G). If y is a vertex of W, then we have either y = e or y = g by Lemma 3.2. If we assume the former, then there would be multiple edges ae, contrary to our assumption. On the other hand, if the latter holds, there is a hexagonal region D''' bounded by a cycle da2e/gx of G. By Lemma 4.4 and the condition (3), D''' is filled only with H2 and we obtain O9(2); the unique inner vertex of degree 3 in D''' must have neighbors {d, e, g}, otherwise, (a) cannot be held.
Therefore we may suppose that y is an inner vertex of D'. In this case, the octagonal region D* bounded by a1yxda2e/g satisfies the conditions of this lemma and hence we can apply the inductive hypothesis to D*; observe that degD„ (y) > 1. Under our assumptions, we fill D* with O9(m) so as not to have adjacent vertices of degree 3, and obtain O9(m + 1); O10 is inappropriate since it yields two adjacent vertices of degree 3 in D.
Next, we assume that there is an inner vertex x of D adjacent to both of b and g. Let D' be an octagonal region bounded by bcda2e/gx; note that the 4-cycle a1bxg bounds a face of G. If D' has a diagonal edge, then the one end should be x since D admits no diagonal. However, if there is such a diagonal, say xd, then there would be a forbidden 2-path bxd, which was already discussed above. Thus D' has no diagonal edge and we can apply Lemma 4.5 to the region. In fact, most cases are excluded by some conditions but we obtain O9(3) and O10 by using O4 and O2, respectively. By the similar argument as above, we obtain O9 (2) (resp., O10) if we assume that there is a 2-path bxe (resp., cx/) for an inner vertex x of D.
Case II. There exists a short 3-path (iii): First, assume that such a short 3-path is a1xyd where x and y are inner vertices of D. In this case, the hexagonal 2-cell region D' bounded by a1xydcb should be filled with either H1 or H2 by Lemma 4.4 and the condition (3) in this lemma. However in each case, D would contain a diagonal or a forbidden 2-path excluded by the above arguments. By the same reason, we do not have to consider a 3-path like bxy/. (Of course, we exclude the paths of the same type, considering the symmetry;
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	175
e.g., a2xyg.)
Case III. There exists a short 4-cycle (iv): We assume that there exists an essential 4-cycle aixyza2 for inner vertices x, y and z of D. Then, D is divided into two octagonal regions D' and D" and they are bounded by aixyza2dcb and aixyza2e/g, respectively. Here, we consider degrees of x and z and first, suppose that degD, (x) = 0. In this case, D' contains a face bounded by aixyw for w e V(G). (Note that degD (z) > 1 and degD„ (z) > 1; otherwise there would be an essential simple closed curve passing through only a and y. Also, degD„ (x) is clearly at least 1.) The vertex w is an inner vertex of D' since if not, D would have a diagonal or a forbidden 3-path by the above argument. Let D''' be the octagonal region bounded by aiwyza2dcb; note that degD,„ (w) > 1. Then both of D'' and D''' satisfy the inductive hypothesis and we fill them with O9(m) or Oi0 so as not to make two adjacent vertices of degree 3 in D. Under the conditions, we only obtain O9(/) if D'' and D''' are filled with O9(/'') and O9 (/''') respectively, where / = /'' + /''' + 1.
Therefore, we may assume that each of degD, (x), degD„ (x), degD, (z) and degD„ (z) is at least 1. Then we also use the inductive hypothesis into D' and D''. However, every case is inappropriate, since using Oi0 yields contractible face by Lemmas 3.8 and 3.12 and using two O9 (m)'s makes y to have degree 2. Thus, the lemma follows.	□
6 Classification by attached cubes
Let G be a P-irreducible quadrangulation of the projective plane. Assume that G has an attached cube H with d(H) = v0viv2v3 and an attached 4-cycle C = m0m1m2m3 such that Mjvj e E(G) for each i e {0,1,2, 3}. Now, observe that any essential cycle of bipartite quadrangulations of the projective plane has even length while that of nonbipartite quadrangulations has odd length. This means that
(I)	G has an essential diagonal 3-curve 7 if G is bipartite or
(II)	G has an essential semi-diagonal 3-curve 7 if G is nonbipartite, such that 7 passes through {v0, v2} by Lemma 3.16.
First, we consider the case (I). In this case, 7 is passing through three faces /1 = v0M0w1v1, /2 = v1m1m2v2 and / = v0av2b for a, b e V(G). Since G is P-irreducible, applying the face-contraction of / at {a, b} breaks the property. However, each of deg(v0) and deg( v2) is clearly at least four and hence we do not have to consider the 3-connectedness of the graph by Lemma 3.12. Thus, we further divide it into the following two cases:
(I-a) The face-contraction of / disturbs the simplicity of the graph.
(I-b) The face-contraction of / yields a quadrangulation with representativity at most 2.
In (I-a), there exists a vertex x adjacent to both a and b such that the 4-cycle C' = v0axb is essential on the projective plane by Lemma 3.10. In this case, we cut the projective plane along C' and obtain (A) in Figure 14. In (I-b), G has a diagonal 3-curve passing through {a, b, x} and three faces /, /' = acxd and /'' = bc'xd' by Lemma 3.8. Considering the identification of vertices except « for i e {1,..., 4}, we obtain (B), (C) and (D) in Figure 14 up to symmetry; we have to pay attention to the simplicity, the degree conditions of the graph and Lemma 4.3, further and that it does not have the structure of (I-a). (For example, if d' = v2 in (B), then we have (C). Furthermore, if x = v3 in (B), then d' (resp.,
176
Ars Math. Contemp. 17 (2019) 153-183
Figure 14: Around an attached cube.
d) must also coincide with v2 (resp., c) by Lemma 4.3 and hence we obtain (D) in the figure. It is not so difficult to confirm that they are all.)
Secondly, we assume the case (II). In this case, G has an essential semi-diagonal 3-curve passing through {v0, u1; v2}, that is, there is an edge joining v0 and v2. We cut open the projective plane along the essential 3-cycle v0v1 v2 and obtain (E) in the figure.
In the first half of the next section, we determine P-irreducible quadrangulations of the projective plane with attached cubes by filling each blank non-quadrilateral region of (A) to (E) with results in Sections 4 and 5.
7 Proof of the main theorem
We shall classify P-irreducible quadrangulations of the projective plane in this section to prove Theorem 1.1, using the lemmas proved in the former sections. For our purpose, we divide our main result into the following four theorems, depending on the existence of an attached cube and bipartiteness.
Theorem 7.1. Let G be a bipartite P-irreducible quadrangulation of the projective plane. If G has an attached cube, then G is one of the graphs shown in Figure 8.
Proof. By the argument in the previous section, we first fill the two non-quadrilateral regions of (A) shown in Figure 14 with H1,..., H17 so as to form a P-irreducible quadrangulation. (However, we implicitly exclude H13 and H15 by Lemma 4.6.) In fact, we consider the hexagonal regions bounded by v0v1v2axb and v0v3v2bxa and fill them with H7, H8, H9, H11; H12, H14, H16 and H17 since we have {v1; v3} n {a, b} = 0; otherwise, G would have multiple edges. When putting a pair of such pieces, we have to check the polyhedrality of G, and the absence of contractible face, removable 4-cycle and shrinkable 2-path, by using Proposition 3.1 and Lemmas 3.8, 3.9, 3.12-3.16.
Checking all the cases is a routine, and hence we present two bad examples below. First, see (i) of Figure 15, which is filled with a pair (H7, H9). However, it is easy to see that this graph has representativity 2. Secondly, see (ii) in the figure with a pair (H11, H12).
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	177
In this case, we can easily find a removable 4-cycle by Lemma 3.16, which is presented as the shaded region in the figure. Similarly to the above two bad cases, we can exclude almost pairs.
Figure 15: Configurations in the proof of Theorem 7.1.
As aresult, 8pairs (Hr, Hn), (#7, H14), (#7, #16), (#7, #17), (#9, #9), (#9, #12), (H9, H14) and (#12, #12) are available and we obtain /4,/5,/6, /7, /8, /9, /10 and /11 in Figure 8, respectively.
Next, we consider (B) in Figure 14. Consider the face-contraction of the face bounded by xdac at {c, d}. Observe that we have no identification of vertices c, d, c' and d' to other white vertices. (It was already done in the previous section.) Thus, we have that deg(x), deg(a) > 4. By Lemma 3.12, the face-contraction breaks the simplicity or the property of representativity at least 3. It is easy to see that the former does not happen and hence we suppose the latter. That is, there is a diagonal 3-curve passing through either {c, d, V2} or {c, d, vo}.
Assume that the curve passes the {c, d, v2} and other two faces f1 and f2 are bounded by dpv2q and v2rcs respectively, for p, q, r, s G V(G). (Actually, by Lemma 4.3, one of p and q, say q, coincides with a. See (iii) in Figure 15.) If s = x in the figure, then it would yield the configuration (C) in the Figure 14; we discuss (C) next. Further, if s = b, then the vertex c is adjacent to both of a and b and hence it would become (A); it was already discussed. Moreover, if r = a, we would have multiple edges v2a. Therefore, we can conclude that the unique possibility of the identification of such vertices is that r = v1 ; note that we have considered all the possibility around f2, since G is bipartite and both of r and s should be black vertices. However, regardless of the unique identification, we can apply the face-contraction of f2 at {r, s} since there is no diagonal 3-curve passing through r and s. This is contrary to G being V-irreducible. By the similar argument, we can find a contractible face when assuming that the diagonal 3-curve passes through {c, d, v0}. As a result, (B) cannot be extended to any V-irreducible quadrangulation.
As the third case, we consider (C) in Figure 14. By Lemma 3.16, there is no attached cube in the hexagonal region D bounded by v0acxv2v1. Therefore, we try to put H1,..., H5 into D. However, by Proposition 3.1 and Lemmas 3.9, 3.15 and 4.3, it is easy to confirm (but routine) that only H1 is available and we have edge v1c in D.
Next, we consider the octagonal region D' bounded by v0v3v2adxc'b. Assume that D' contains another attached cube A such that d (A) = v0v1 v2 v3. Then its one cube diagonal pair, now say {v0, v2}, coincides with either {a, b} or {c', v2} since it should be facing by Lemma 3.16. If the former occurs, then it clearly causes /1, /2 or /3 by Lemmas 4.4 and 4.6. Thus, we suppose the latter (see (iv) of Figure 15). Now we fill the two hexagonal regions
178
Ars Math. Contemp. 17 (2019) 153-183
H and H' bounded by v0v1v2v3c'b and v2acxc'v'1, respectively. However, H admits only H12 and H14, and H' does only H8 by considering their partial structures. Therefore, we obtain /12 and /13 in Figure 8 in this case.
Then, we consider the possibility of existence of diagonal edges in the octagonal region D' and conclude that either v3c' or v3d is available by some lemmas and P-irreducibility. If both of diagonals are taken as edges of G, then G becomes /14. If one of two diagonals, say v3c', is used, then we find the hexagonal region H bounded by c'v3v2acx; note that H does not contain its diagonal. We put H2, H3, H4 and H5 into H, however each of the resulting graphs has a contractible face; it is actually reducible into /14. Furthermore, the same argument works when we use the diagonal v3d.
Therefore we may assume that D' in (C) contains no attached cube and no diagonal, that is, it satisfies the condition of Lemma 4.5. Now, we try to put Oj for j G {1,..., 8} into D'. Considering some lemmas in Section 3, we have only /15 from this case by filling it with O2 in Figure 7.
Similarly to (C), we consider the inside of octagonal region O bounded by cycle v0v3v2adv1 c'b in the case (D). However, the argument is almost the same as the previous one and just a routine and hence we omit it here. (We first discuss the existence of an attached cube and diagonals in O. Next, we put the configurations of Figure 7.) As a result, we obtain /16 /17 from (D). Therefore, the theorem follows.	□
We define I18 [2; s1,..., sn] as a graph obtained from (E) in Figure 14 by putting H18[s1,..., sn] inside the hexagonal region. Recall that we forbid /18[2;..., 2,2,...], /18[2;..., 3,3,...], /18[2; 2,...] and /18[2;..., 3], since we make it a rule to unify consecutive Q2's to one.
Theorem 7.2. Let G be a nonbipartite P-irreducible quadrangulation of the projective plane. If G has an attached cube, then G is one of /18 [2; s1,..., sn], /19 and /20 shown in Figure 11.
Proof. By the argument in the previous section, we have (E) in Figure 14 in this case. There is the unique blank hexagonal region D which satisfies the conditions of Lemma 5.4. Hence, we fill D with H18[s1,..., sn] (resp., H20) and obtain /18[2; s1,..., sn] (resp., /19); note that H21 was already discussed in Lemma 5.1 and we obtained /20.
In fact, some of /18 [2; s1,..., sn] with short sequences cannot satisfy the polyhedrality, hence we should exclude such "bad" sequences, which are listed in Table 1. It is not difficult to confirm that if n > 4, then any /18[2; s1,..., sn] satisfying the above rule is acceptable. (Observe that there are different sequences [s1,... , sn] = [s1,..., s^] such
that /18 [2; s1,..., s„] = /18 [2; s1,..., s^]; e.g., /18 [2; 1,1,2] = /18 [2; 3,1,1] in the table.)
□
Figure 16 presents six bipartite P-irreducible quadrangulations of the projective plane without attached cubes. In the figure, /26(2n + 1) (n > 2) represents an infinite series of such graphs. The center white vertex of /26(2n +1) has degree 2n +1 and each its black neighbors has degree 4. Furthermore, it has 2n +1 vertices of degree 3 on the essential simple closed curve drawn by dotted circle. (We obtain the projective plane by identifying all pairs of antipodal points of the dotted circle.) In fact, the figure represents /26(7) with 15 vertices.
Theorem 7.3. Let G be a bipartite P-irreducible quadrangulation of the projective plane. If G has no attached cube, then G is one of the graphs shown in Figure 16.
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane
179
Table 1: Good and bad sequences for [s1,..., sn] (n < 3).
[S1, ...,Sn] (n < 3)_
[1]	bad (rep. 2)
[1.1],	[3,2]	good
[1.2],	[3,1]	bad (rep. 2)
[1,1,1], [1,1, 2], [1, 2,1], [1, 3,1], [1, 3, 2], [3,1,1], [3,1, 2], [3, 2,1] good
Proof. For brevity, we write only the outline of the proof. We divide the proof into the following three cases by Lemmas 3.5, 3.13 and 3.15. Note that we prove those cases in this order, that is, we implicitly exclude a graph already appeared in the former cases.
Case I. G has a 2-path u0u1u2 induced by three vertices of degree 3: See (i) in Figure 17. In the figure, each antipodal pair of points of the dotted circle should be identified to obtain the projective plane. Note that v0v1v2v3v4v5 is a cycle of G since if v3 = v5, then deg(v4) = 3 and G would contain an attached cube.
The 2-path u0u1u2 is not shrinkable and hence we have a face v0bv2b' by Lemma 3.14. Furthermore, we consider the face-contraction of the face v2v3v4u2 at {v3,u2}. Since deg(v2), deg(v4) > 4, we do not have to pay attention to the connectivity of the resulting graph by Lemma 3.12. Also, since u1 is an inner vertex of the hexagon, the face-contraction preserves the simplicity of the graph. Hence, by Lemma 3.8, we have a face v3cv1c'. By the same way, we find a face v5av1a' (see the figure again).
Similarly to the argument in Section 6 and the previous theorem, we consider the possibility of identification of vertices and fill blank non-quadrilateral regions with H1,..., H5 in Lemma 4.4. As a result, we obtain 121,122 and 123 from this case.
24
25
I26(2n + 1) (n > 2)
Figure 16: The 6 families of bipartite P-irreducible quadrangulations without an attached cube.
180
Ars Math. Contemp. 17 (2019) 153-183
Case II. G has two adjacent vertices x and y of degree 3: See the inside of the hexagon in (ii) of Figure 17. Note that each of deg(v0), deg(v2), deg(v3) and deg(v5) is at least 4 since there is no 2-path induced by vertices of degree 3 by the previous argument. As well as Case I, we consider face-contractions of v1v2xv0 at {v1; x} and v3v4v5y at {v4, y}. By Lemma 3.8, we have two diagonal 3-curves 7 and 7' passing through {v1; x} and {v4, y}, respectively. We may assume that 7 passes v3 as the third vertex, up to symmetry.
If 7' passes v2, then it (resp., 7) goes through v2av4a' (resp., v16v36') in (ii) of Figure 17. We consider the identification of vertices and further fill the blank non-quadrilateral regions, and obtain /24 and /25. On the other hand, if 7' passes v0 as the third vertex, then both of 7 and 7' pass a common face v0v1v4v3 (see (iii) in the figure). However, we can fill the unique hexagonal region with neither H1; H2 nor H3 in Figure 6.
Case III. All vertices of degree 3 are independent: Let x be a vertex of degree 3 having neighbors {v0,v2,v4} and v0v1 v2v3v4v5 as its link walk. By the assumption, each of deg(v0), deg(v2) and deg(v4) is at least 4. We consider face-contractions of three faces incident to x and have some cases depending on the forbidden structure of the resulting graph. (For example, if each operation yields multiple edges, we have (iv) in Figure 17, but it is immediately excluded since we can find a simple closed curve intersecting G at only {v0, v2}.) Further, we try to identify vertices as well as the previous cases but most cases are not suited other than the following one case.
See (v) in Figure 17 that has the unique blank octagonal region D bounded by a closed walk v1v2v3av5v4v3b. Note that each of degD(v2), degD(v4), degD(a) and degD(b) is at least 1, since G has no vertex of degree 2 and no two adjacent vertices of degree 3. Therefore, D satisfies the conditions of Lemma 5.5. However, putting either Og(21 + 1) (l > 1) or O10 in Figure 13 into D would yield two adjacent vertices of degree 3. Actually, when filling D with Og(2Z) (l > 1), we obtain /25(2/ + 3) = /25(2(1 + 1) + 1). Then, we got the conclusion of the theorem.	□
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	181
As well as /is [2; si,..., sn], we can naturally define lis[1; si,..., sn] by using (iii) of Figure 18 which also has the unique hexagonal region.
Figure 18: Structures of nonbipartite P-irreducible quadrangulations with no attached cube.
Theorem 7.4. Let G be a nonbipartite P-irreducible quadrangulation of the projective plane. If G has no attached cube, then G is isomorphic to /18[1; 1,..., 1].
Proof. As well as the proof of Theorem 7.3, we divide our argument into the following three cases.
Case I. G has a 2-path m0u1m2 induced by three vertices of degree 3: See (i) in Figure 18. Since G is nonbipartite, we have three semi-diagonal 3-curves passing through {v0,u1,v2}, {v1;w2,w3} and {v1;w0,v5}, respectively. (Consider the 23-path shrink m0m1m2 and face-contractions of v2v3v4u2 and v4v5v0u0.) Under the conditions, there should be three edges v0v2, v1v3 and v1v5 since v0v1v2v3v4v5 forms a cycle of G. By Lemma 4.3, the quadrilateral region v1v2v0v5 corresponds to a face of G. However, there is an essential simple closed curve passing through only v0 and v1, a contradiction.
Case II. G has two adjacent vertices x and y of degree 3: See (ii) in Figure 18. Note that each of deg(v0), deg(v2), deg(v3) and deg(v5) is at least 4. Suppose that v0v1v2v3v4v5 is a cycle of G. We consider the face-contraction of v0v1v2x (resp., v3v4v5y) at {v1; x} (resp., {v4, y}). Then, there are two semi-diagonal 3-curves and hence we have v1v3, v2v4 G E(G), up to symmetry. Clearly, we find an essential simple closed curve intersecting G at only {v2, v3}, a contradiction.
Therefore, we assume that v0v1v2v3v4v5 is not a cycle of G. Under the conditions, v1 and v4 must coincide and the other vertices of the closed walk are distinct (see (iii) in Figure 18). Then the configuration contains a blank hexagonal region v1v2v3v4(= v1 )v0v5 and it satisfies the conditions of Lemma 5.3. Now, we apply the result of the lemma. But, H19 is excluded immediately since it contains an attached cube. In this case, H18 [1,..., 1] only fits the region. The resulting graph is clearly /18[1; 1,..., 1].
Case III. All vertices of degree 3 are independent: Do the same procedure as in the previous theorem. (Begin with considering face-contractions of three faces incident to a vertex of degree 3.) However, we obtain no P-irreducible quadrangulation from this case; since two adjacent vertices of degree 3 often appear. Therefore, the theorem follows.	□
182
Ars Math. Contemp. 17 (2019) 153-183
References
[1]	D. Archdeacon, J. Hutchinson, A. Nakamoto, S. Negam and K. Ota, Chromatic numbers of quadrangulations on closed surfaces, J. Graph Theory 37 (2001), 100-114, doi:10.1002/jgt. 1005.
[2]	V. Batagelj, An inductive definition of the class of 3-connected quadrangulations of the plane, Discrete Math 78 (1989), 45-53, doi:10.1016/0012-365x(89)90159-3.
[3]	G. Brinkmann, S. Greenberg, C. Greenhill, B. D. McKay, R. Thomas and P. Wollan, Generation of simple quadrangulations of the sphere, Discrete Math. 305 (2005), 33-54, doi:10.1016/j. disc.2005.10.005.
[4]	H. J. Broersma, A. J. W. Duijvestijn and F. Gobel, Generating all 3-connected 4-regular planar graphs from the octahedron graph, J. Graph Theory 17 (1993), 613-620, doi:10.1002/jgt. 3190170508.
[5]	P. Eades, S.-H. Hong, N. Katoh, G. Liotta, P. Schweitzer and Y. Suzuki, A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system, Theoret. Comput. Sci. 513 (2013), 65-76, doi:10.1016/j.tcs.2013.09.029.
[6]	D. Hudak, T. Madaras and Y. Suzuki, On properties of maximal 1-planar graphs, Discuss. Math. Graph Theory 32 (2012), 737-747, doi:10.7151/dmgt.1639.
[7]	J. P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, J. Comb. Theory Ser. B 65 (1995), 139-155, doi:10.1006/jctb.1995.1047.
[8]	W. Liu and Y. Chen, Polyhedral embeddings of snarks with arbitrary nonorientable genera, Electron. J. Combin. 19 (2012), #P14 (6 pages), https://www.combinatorics.org/ ojs/index.php/eljc/article/view/v19i3p14.
[9]	B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395-401, doi:10.1007/s004930100003.
[10]	B. Mohar and N. Robertson, Flexibility of polyhedral embeddings of graphs in surfaces, J. Comb. Theory Ser. B 83 (2001), 38-57, doi:10.1006/jctb.2001.2036.
[11]	B. Mohar and A. Vodopivec, On polyhedral embeddings of cubic graphs, Combin. Probab. Comput. 15 (2006), 877-893, doi:10.1017/s0963548306007607.
[12]	T. Nagasawa, K. Noguchi and Y. Suzuki, No optimal 1-planar graph triangulates any nonori-entable closed surface, J. Graph Theory 89 (2018), 350-360, doi:10.1002/jgt.22255.
[13]	M. Nagashima, A. Nakamoto, S. Negami and Y. Suzuki, Generating 3-connected quadrangula-tions on surfaces, Ars Combin. 116 (2014), 371-384.
[14]	A. Nakamoto, Irreducible quadrangulations of the Klein bottle, Yokohama Math. J. 43 (1995), 125-139, http://hdl.handle.net/10131/5655.
[15]	A. Nakamoto, Irreducible quadrangulations of the torus, J. Comb. Theory Ser. B 67 (1996), 183-201, doi:10.1006/jctb.1996.0040.
[16]	A. Nakamoto, Triangulations and Quadrangulations on Surfaces, Ph.D. thesis, Keio University, Japan, 1996.
[17]	A. Nakamoto, Generating quadrangulations of surfaces with minimum degree at least 3, J. Graph Theory 30 (1999), 223-234, doi:10.1002/(sici)1097-0118(199903)30:3(223::aid-jgt7) 3.3.co;2-d.
[18]	A. Nakamoto and K. Ota, Note on irreducible triangulations of surfaces, J. Graph Theory 20 (1995), 227-233, doi:10.1002/jgt.3190200211.
Y. Suzuki: Generating polyhedral quadrangulations of the projective plane	183
[19]	A. Nakamoto and Y. Suzuki, Diagonal slides and rotations in quadrangulations on the sphere, Yokohama Math. J. 55 (2010), 105-112, http://hdl.handle.net/10131/ 00011358.
[20]	S. Negami and A. Nakamoto, Diagonal transformations of graphs on closed surfaces, Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem. 40 (1993), 71-97.
[21]	K. Noguchi and Y. Suzuki, Relationship among triangulations, quadrangulations and optimal 1-planar graphs, Graphs Combin. 31 (2015), 1965-1972, doi:10.1007/s00373-015-1568-8.
[22]	N. Robertson and R. Vitray, Representativity of surface embeddings, in: B. Korte, L. Lovasz, H. J. Promel and A. Schrijver (eds.), Paths, Flows, and VLSI-Layout, Springer, Berlin, volume 9 of Algorithms and Combinatorics, 1990 pp. 293-328, papers from the meeting held at the University of Bonn, Bonn, June 20 - July 1, 1988.
[23]	Y. Suzuki, Optimal 1-planar graphs which triangulate other surfaces, Discrete Math. 310 (2010), 6-11, doi:10.1016/j.disc.2009.07.016.
[24]	Y. Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math. 24 (2010), 1527-1540, doi:10.1137/090746835.
[25]	Y. Suzuki, Cube-contractions in 3-connected quadrangulations, Ars Math. Contemp. 10 (2016), 281-290, doi:10.26493/1855-3974.552.bf3.
[26]	Y. Suzuki and T. Watanabe, Generating even triangulations of the projective plane, J. Graph Theory 56 (2007), 333-349, doi:10.1002/jgt.20269.