N-Flips in Triangulations with Two Odd Degree Vertices

Abstract

In this paper, we prove that any two triangulations G and $G'$ on the sphere with exactly two odd degree vertices can be transformed into each other by two local transformations, called an N-flip and a $P_2$-flip, preserving the parity of degree of each vertex, if $|V(G)|=|V(G')|$. This is an analogy of the same result for triangulations with each vertex even degree [7], but we prove such a fact does not hold for triangulations with at least four odd degree vertices.

1 Introduction

A triangulationG on a closed surface $F^2$ is a fixed embedding of a simple graph on $F^2$ such that each face of G is bounded by a 3-cycle, where a k-cycle means a cycle of length k. A k-vertex is a vertex of degree k and an even (resp., odd) vertex is a vertex of even (resp., odd) degree. For a vertex v of G, the link of v is the boundary cycle of the 2-cell region formed by all faces incident to v. A k-region is a 2-cell region bounded by a closed walk of length k. A face (or a region) R of a graph G is even (resp., odd) if R is bounded by a closed walk of even (resp., odd) length.

Let $v_1v_2v_3$ and $v_1v_3v_4$ be two triangular faces of a triangulation G sharing an edge $v_1v_3$. A diagonal flip of $v_1v_3$ is to replace the diagonal $v_1v_3$ with $v_2v_4$ in the quadrilateral $v_1v_2v_3v_4$, as shown in Fig. 1. When the transformation breaks the simpleness of G, we do not apply it.

Fig. 1

The diagonal flip

Wagner proved that any two triangulations on the sphere with the same number of vertices can be transformed into each other by a sequence of diagonal flips [13]. Moreover, Negami has extended this result to all closed surfaces and proved that any two triangulations on the same closed surface can be transformed into each other by diagonal flips if they have the same and sufficiently large number of vertices [9]. For related results, see the survey [10].

Observe that a diagonal flip changes the parity of degree of vertices. Hence we consider the following transformation, called an N-flip, preserving the parity of degree of each vertex in a triangulation. This was first defined by Nakamoto et al. in [7].

Let G be a triangulation. Suppose that G has a hexagonal region bounded by a cycle $v_1v_2v_3v_4v_5v_6$ with edges $v_1v_5,v_2v_4,v_2v_5$ and there is no other vertices and edges in the region. The N-flip of the path $v_1v_5v_2v_4$ is to remove $v_1v_5,v_2v_4,v_2v_5$ and add $v_1v_3,v_3v_6,v_4v_6$, as shown in Fig. 2. When the transformation breaks the simpleness of G, we do not apply it. Two triangulations G and $G'$ are N-equivalent, denoted by $G \sim _N G'$, if G and $G'$ can be transformed into each other by a sequence of N-flips.

A triangulation G is even if each vertex of G has even degree. Since an even triangulation G on the sphere has a unique 3-coloring [12], V(G) can uniquely be decomposed into three partite sets $V_R(G), V_B(G)$ and $V_Y(G)$ colored by red, blue and yellow, respectively. We call $(|V_R(G)|, |V_B(G)|,|V_Y(G)|)$ the tripartition size of G. An N-flip always preserves the tripartition of a triangulation, as shown in Fig. 2. Hence if G and $G'$ are N-equivalent, then they have the same tripartition size. Nakamoto et al. [7] proved that the converse also holds.

Theorem 1

(Nakamoto et al. [7]) Two even triangulations on the sphere can be transformed into each other by a sequence ofN-flips if and only if they have the same tripartition size.

If two even triangulations G and $G'$ have the same number of vertices but distinct tripartition size, then G and $G'$ cannot be transformed into each other only by N-flips. So consider another transformation changing the tripartition size. Let v be a vertex of G with the link $v_1 \dots v_k$$(k \ge 3)$ . Put two vertices x, y on the edge $vv_1$ and join them to $v_2$ and $v_k$. The $P_2$-flip of x, y is to move x, y to the edge $vv_2$ and join them to $v_1$ and $v_3$, as shown in Fig.  3. Similarly to N-flips, if the transformation breaks the simpleness of G, we do not apply it. A $P_2$-flip preserves the parity of degree of each vertex, but it changes the tripartition size, as we can see that in Fig.  3. Then by using $P_2$-flips in addition to N-flips, they proved the following theorem:

Fig. 2

The N-flip

Fig. 3

The $P_2$-flip

Theorem 2

(Nakamoto et al. [7]) Any two even triangulations on the sphere with the same number of vertices can be transformed into each other by a sequence ofN- and $P_2$-flips.

The N- and $P_2$-flips in even triangulations have also been considered for non-spherical surfaces [5, 8]. Since every non-spherical surface admits non-3-colorable even triangulations, we can find two even triangulations with the same number of vertices which cannot be transformed by the two operations, that is, a 3-colorable one and a non-3-colorable one. We note that the N- and $P_2$-flips preserve the 3-colorability of graphs. Moreover, the paper [5] has introduced an algebraic invariant, called the monodromy, such that if two even triangulations on a surface can be transformed by the two operations, then their invariants coincide [4, 5]. For other related researches, see [6] for example.

In this paper, we would like to consider whether two triangulations G and $G'$ on the sphere can be transformed by N- and $P_2$-flips if G and $G'$ have the same number of vertices and the same number of odd degree vertices.

A k-odd triangulation is one with exactly k odd vertices. We note that k must be even by the Handshaking Lemma. In this paper, we prove the following result for 2-odd triangulations:

Theorem 3

Any two 2-odd triangulations on the sphere with the same number of vertices can be transformed into each other by a sequence ofN- and$P_2$-flips.

For even triangulations, the $P_2$-flip is necessary to change the tripartition size. (Also the N-flip is necessary to transform an even triangulation on the sphere without adjacent 4-vertices into another.) However, since a 2-odd triangulation on the sphere is not 3-colorable, what can we say about the necessity of $P_2$-flips in 2-odd triangulations?

We prove the following theorem for 2-odd triangulations without $P_2$-flips, introducing the color factorU(G) of a 2-odd triangulation G, where the color factor of G is a unique vertex subset of G whose definition will be given in Sect. 2.

Theorem 4

LetG and$G'$ be 2-odd triangulations on the sphere with$|V(G)|=|V(G')|$ and$|U(G)|=|U(G')|$. ThenG and$G'$ can be transformed into each other only byN-flips.

Theorems 3 and 4 are an analogy of Theorems 2 and 1 for 2-odd triangulations, respectively. However, we surprisingly give the following negative result for k-odd triangulations with any even integer $k \ge 4$.

Theorem 5

For any even integer$k \ge 4$ and any integer$h \ge 1$, there exists a pair ofk-odd triangulationsG and$G'$ on the sphere with$|V(G)|=|V(G')| \ge h$ which cannot be transformed into each other byN- and$P_2$-flips.

In Sect. 2, we define the notion “face subdivision” and “color factor” which plays an essential role, and using them, we prove Theorem 5. In Sect. 3, we establish a generating theorem for 2-odd triangulations on the sphere. In Sect. 4, we show several lemmas and give a proof of Theorem 3. Finally, in Sect. 5, we prove Theorem 4.

2 Face Subdivision and Color Factor

Let D be a simple graph 2-cell embedded on a surface $F^2$. The face subdivision of D, denoted by $\mathrm{FS}(D)$, is the triangulation on $F^2$ obtained from D by putting a single vertex into each face of D and joining it to all vertices on the corresponding boundary walk. The set of added vertices in $\mathrm{FS}(D)$ is the color factor of $\mathrm{FS}(D)$. It should be observed that each vertex of D has even degree in $\mathrm{FS}(D)$, and hence no two odd vertices are adjacent in $\mathrm{FS}(D)$. A triangulation G on $F^2$ is a face subdivision if there exists a graph D on $F^2$ such that $G=\mathrm{FS}(D)$. In this case, D is the frame of G, and an edge $e \in E(G)$ is a frame edge (resp., a spoke) if $e \in E(D)$ (resp., $e \notin E(D)$).

The following proposition holds for 2-odd triangulations on the sphere.

Proposition 6

Every 2-odd triangulation on the sphere is a face subdivision with a unique frame.

The proof of Proposition 6 is postponed to the next section. Before it, we describe several facts obtained by Proposition6, assuming that the proposition is true.

Let G be a 2-odd triangulation. Then, by Proposition 6, the color factor U(G) can be taken in G uniquely. Moreover, we see that an N-flip always preserves U(G) but a $P_2$-flip does not, as shown in Fig. 4. Hence we have the following.

Fig. 4

N-flips and $P_2$-flips in a face subdivision G

Proposition 7

LetG be a triangulation on a surface$F^2$, and let$G'$ and$G''$ be triangulations obtained fromG by a singleN-flip and a single$P_2$-flip, respectively. IfG is a face subdivision, then so are both$G'$ and$G''$, and furthermore, $|U(G)|=|U(G')|$.

Proof

Let $v_1v_5,v_5v_2$ and $v_2v_4$ be diagonals of a 6-region in G which are flipped by an N-flip, and let $v_1v_3, v_3v_6$ and $v_6v_4$ be the resulting diagonals (as in Fig.  2). Then, by the definition of the face subdivision, one of the following always holds:

• (i) Both $v_1$ and $v_4$ are color factors of G, or

• (ii) either $v_2$ or $v_5$ is a color factor of G.

Otherwise, G has a face consisting only of vertices which are not in the color factor, or G has adjacent two vertices in the color factor, a contradiction. Therefore, as shown in the left of Fig.  4, the proposition holds since any N-flip preserves U(G). Similarly, we can prove that $G''$ is a face subdivision (see the right of Fig. 4). $\square$

By Proposition 7, we can prove Theorem 5.

Proof of Theorem 5

Let $k \ge 4$ be an even integer and let $h \ge 1$ be an integer. Let Q be a 3-connected quadrangulation (i.e., one with each face bounded by a 4-cycle) on the sphere with m vertices. Take $\frac{k}{2}$ distinct faces $f_1,\ldots ,f_{\frac{k}{2}}$ in Q such that $f_1=xyzw$ shares the edge xy with $f_2$, where we have $\frac{k}{2} \le m-2$ since Q has $m-2$ faces by Euler’s formula. Put a single diagonal to $f_i$ for $i \in \{1, \dots , {\frac{k}{2}}\}$ so that $f_1$ receives the diagonal xz. Then resulting graph $Q'$ has exactly k triangular faces and all others quadrilateral. We note that $Q'$ is simple. (For, if two added diagonals join the same pair of vertices, say p, q, then $Q-\{p,q\}$ is disconnected, contrary to the 3-connectedness of Q.) Let $G=\mathrm{FS}(Q')$, which is a k-odd triangulation with $m+(m-2-\frac{k}{2})+k=2m+\frac{k}{2}-2$ vertices. Taking m large, we may suppose that $|V(G)| \ge h$.

Let $a,b \in V(G)$ be two vertices of the color factor of G which are added to the triangular faces xyz and xzw, respectively. Let $G'$ be the triangulation obtained from G by a single diagonal flip of the edge xz. Then $G'$ is a k-odd triangulation, in which x and z are odd, a and b are even and the degree of other vertices are unchanged. Observe that x is adjacent to a 3-vertex in $G'$, say c, since two 3-vertices are added to two triangular faces of $f_2$. Hence x and c are two neighboring odd vertices in $G'$, and hence $G'$ is never a face subdivision, by the observation in the first paragraph of this section. By Proposition 7, G and $G'$ are k-odd triangulations with $|V(G)|=|V(G')| \ge h$ but cannot be transformed into each other by N- and $P_2$-flips. $\square$

3 A Generating Theorem for 2-Odd Triangulations

In the rest of this paper, a 2-odd triangulation means one on the sphere. Let G be a 2-odd triangulation and let v be a 4-vertex in G with link $v_1v_2v_3v_4$. The 4-contraction of v at $\{v_1,v_3\}$ is to remove v, identify $v_1$ and $v_3$, and replace two pairs of multiple edges $\{ v_1v_2 , v_3v_2 \}$ and $\{ v_1v_4 , v_3v_4 \}$ with two single edges $v_1v_2$ and $v_1v_4$, respectively, as shown in Fig. 5. We call the new vertex arisen by the identification $v_1=v_3$ the image of the 4-contraction and denoted by $[v]_{v_1=v_3}$. If this operation breaks the simpleness or changes the number of odd vertices in G, then we do not apply it. The inverse operation is called a 4-splitting. By the definition, a 4-contraction transforms G into a 2-odd triangulation with $|V(G)|-$ 2 vertices.

Let $u_1u_2u_3$ be a face in G and let $v_1v_2v_3$ be a 3-cycle in G such that 3-cycles $v_iu_ju_k$ and $v_iv_ju_k$ bound faces for $\{i,j,k\}=\{1,2,3\}$, where these six vertices form the octahedron in G. The octahedron removal is to remove $u_1,u_2$ and $u_3$ (see Fig. 6), and the inverse operation is an octahedron addition. Note that these transformations always preserve the simpleness of graphs and the number of odd vertices in G (Fig. 7).

Fig. 5

The 4-contraction

Fig. 6

The octahedron removal

Fig. 7

The graph $C_3 + \bar{K_2}$

By using the above operations, we establish a generating theorem for 2-odd triangulations. A 2-odd triangulation G is minimal if neither a 4-contraction nor an octahedron removal can be applied to G.

Lemma 8

Letx andy be odd vertices of a 2-odd triangulation. Thenx andy are not adjacent.

Proof

It is shown in [3] that if a 2-odd triangulation on any surface has two adjacent odd vertices, then it is not 4-colorable. Thus, by Four Color Theorem [1], two odd vertices are not adjacent in G. $\square$

The following lemma is useful in a proof of Theorem 10. In fact, the following is already proved for even triangulations on any surface in [11]. We can mostly apply their proof to the proof of the following lemma since each inner vertex in the region has even degree. However, to make the paper be self-contained, we write the proof of the following.

Lemma 9

LetG be a 2-odd triangulation on a surface which is minimal with respect to 4-contractions and octahedron removals.

• (i) Let$\Delta$ be a 3-region ofG which contains no odd vertex in its interior. Then$\Delta$ bounds a face ofG.

• (ii) Let$\Gamma$ be a 4-region ofG bounded by a 4-cycleabcd, which contains no odd vertex in its interior. Then the interior of$\Gamma$ has either a single diagonal, a single 4-vertex, or$Q^{(m)}$ for some$m \ge 1$, as shown in Fig.  8, where$Q^{(m)}$ consists ofm paths$bu_1v_1d,bu_2v_2d,\dots ,bu_mv_md$ and$m-1$ vertices$p_1,\dots ,p_{m-1}$ of degree 6, in which$\deg (u_i)=\deg (v_i)=4$ for each$i \in \{1,\dots ,m\}$, $p_j$ is adjacent to$b,d,u_{j},v_{j},u_{j+1},v_{j+1}$ for each$j \in \{1,\dots ,m-1\}$, and$av_1, au_1, cv_m, cu_m \in E(G)$.

Proof

(i) Let uvw be the boundary 3-cycle of $\Delta$ which does not bound a face of G and suppose that $\Delta$ contains no odd vertex in its interior. Take $\Delta$ to be innermost and regard it as a plane triangulation H with boundary cycle uvw. Note that any vertex of H except u, v, w has even degree. By Euler’s formula, we find that H has at least four vertices of degree at most 5. Therefore, there exists a vertex x of degree 4 in $\Delta$ with its link $x_1x_2x_3x_4$. Since x is not contractible at $\{x_i, x_{i+2}\}$ for any $i = 1,2$, there are 3- or 4-cycles $C_1$ and $C_2$ passing through $x_1xx_3$ and $x_2xx_4$, respectively. If one of $C_1$ and $C_2$, say $C_1$, passes outside of $\Delta$, then both of $x_1$ and $x_3$ lie on uvw. In this case, $x_1xx_3$ would be a smaller contractible 3-cycle which does not bound a face, a contradiction. Thus, both $C_1$ and $C_2$ are included in $\Delta$, and hence they cross at x and another vertex y in $\Delta$. Since every 3-cycle, except uvw, bounds a face by the assumption on $\Delta$, we can find a removable octahedron (induced by $\{x,x_1,x_2,x_3,x_4,y\}$) in G, which contradicts that G is minimal.

(ii) We prove the lemma by induction on the number $F \ge 2$ of faces in $\Gamma$. If $F = 2$, then we are done since $\Gamma$ has a diagonal edge. So we may suppose that $F \ge 3$ and $\Gamma$ has no diagonal edge. Hence, by using Euler’s formula, $\Gamma$ contains a 4-vertex x in its interior (cf. [11, Lemma 5]).

Let $L_x=x_1x_2x_3x_4$ be the link of x. If $L_x$ coincides with the boundary cycle abcd of $\Gamma$, then $\Gamma$ is isomorphic to the center of Fig. 8. Moreover, if $x_1 = a, x_2 = b$ and $x_3 = c$, then the smaller 4-region $R=av_4cd$ is isomorphic to one of 4-regions shown in Fig. 8 by induction. (By Lemma 9(i), $L_x$ should be put in $\Gamma$ so that no edge of $L_x$ is a diagonal of $\Gamma$.) Noting that $\Gamma$ contains no odd vertex, $\Gamma$ is $Q^{(1)}$ if R has a diagonal, and R contains a contractible 4-vertex in its interior if otherwise. Thus, by symmetry, $L_x$ and the 4-cycle abcd share at most two vertices.

First suppose that $L_x$ and the 4-cycle abcd share at most one vertex, say $x_1 = a$. Since x is not contractible, let $C_1$ and $C_2$ be 3- or 4-cycles passing through $x_1xx_3$ and $x_2xx_4$, respectively. By the assumption, all vertices of $C_1$ and $C_2$ lie in the interior of $\Gamma$ and both cycles are of length 4 by Lemma 9(i), that is, there exists a vertex u in $\Gamma$ such that $C_1=xx_1ux_3$ and $C_2=xx_2ux_4$ by the planarity. Note that each edge of $C_2$ lies in the interior of $\Gamma$ since $\{x_2,x_4\} \cap \{a,b,c,d\} = \emptyset$. If $C_1$ also lies in $\Gamma$, then without loss of generality, $x_1(=a)x_4u$ bounds a 3-region containing $x,x_2$ and $x_3$ in its interior, contrary to Lemma 9(i). Thus, avoiding a non-facial 3-cycle in $\Gamma$, we may suppose that $u=c$ and that $ux_1$ lies outside of $\Gamma$. Hence, by symmetry, $\Gamma$ is separated to three 4-regions bounded by $R_1=x_1bcx_2$, $R_2=x_1x_2cx_4$ and $R_3=x_1x_4cd$, respectively. Observe that $R_2$ includes two adjacent 4-vertices x and $x_3$ and that by induction, each of $R_1$ and $R_3$ is isomorphic to one of 4-regions shown in Fig. 8. By Lemma 9(i) and the non-existence of odd inner vertices in $\Gamma$, both $R_1$ and $R_3$ are isomorphic to $Q^{(m_1)}$ and $Q^{(m_2)}$ for some $m_1,m_2 \ge 1$. Hence, $\Gamma$ is isomorphic to $Q^{(m)}$ for $m = m_1 + m_2 + 1$. (By the parity of $\deg _G(x_2)$ and $\deg _G(x_4)$, we can uniquely embed $Q^{(m_1)}$ and $Q^{(m_2)}$ into $R_1$ and $R_3$, respectively.)

Therefore, we finally suppose that $L_x$ and the 4-cycle abcd share exactly two vertices. By Lemma 9(i), $\Gamma$ does not contain a non-facial 3-region. Thus, by symmetry, we have two cases; (1) $x_1 = a$ and $x_3 = c$ and (2) $x_1 = a$ and $x_2 = b$.

For the former case, we can apply a 4-contraction of x at $\{x_2,x_4\}$, a contradiction. So we suppose that the case (2) occurs. Similarly to the argument in the above cases, there are 3- or 4-cycles $C_1$ and $C_2$ passing through $x_1xx_3$ and $x_2xx_4$, respectively. In particular, by Lemma 9(i), each of those cycles has length 4 since $\{x_3,x_4\} \cap \{a,b,c,d\} = \emptyset$, and then we let $C_1 = xx_1ux_3$ and $C_2 = xx_2vx_4$. If at least one of u and v is contained in the interior of $\Gamma$, then we have a 3-region in $\Gamma$ containing $x,x_3$ and $x_4$ in its interior, contrary to Lemma 9(i). Thus, each of u and v coincides with c or d by the simplicity and Lemma 9(i).

By symmetry, we first consider $u = v = c$. In this case, a 4-region $ax_4cd$ in $\Gamma$ is isomorphic to one of 4-regions shown in Fig. 8. Similarly to the above arguments, we have that $\Gamma$ is isomorphic to $Q^{(m)}$ for some $m \ge 2$. Next, we let $u = c$ and $v = d$. In this case, a 4-region $x_3cdx_4$ in $\Gamma$ cannot be isomorphic to any 4-region shown in Fig. 8, for otherwise, $x_3$ or $x_4$ must be an odd vertex, contrary to the assumption. Therefore, the lemma holds. $\square$

Fig. 8

The interior of $\Gamma$ bounded by the 4-cycle abcd, a single diagonal, a single 4-vertex and $Q^{(m)}$ with $m=3$

Theorem 10

Every 2-odd triangulation on the sphere can be obtained from$C_3 + \bar{K_2}$ by a sequence of 4-splittings and octahedron additions, where$C_3 + \bar{K_2}$ is the 2-odd triangulation shown in Fig. 7.

Proof

Let G be a minimal 2-odd triangulation, and so we shall prove $G=C_3 + \bar{K_2}$. Observe that a triangulation on the sphere has at least four vertices, and that one with exactly four vertices must be a tetrahedron. If $|V(G)|=5$, then G is isomorphic to $C_3 + \bar{K_2}$, since it is a unique triangulation with five vertices. Hence we suppose that $|V(G)|\ge 6$.

It is known that every triangulation on the sphere (with at least four vertices) contains at least four vertices of degree at most 5. Hence, G contains a 4-vertex since G is a 2-odd triangulation. Then let v be a 4-vertex in G with link $v_1v_2v_3v_4$.

Consider the 4-contraction of v at $\{v_1,v_3\}$ in G. If the resulting graph ${\tilde{G}}$ is still a 2-odd triangulation, then this contradicts the minimality of G. Hence ${\tilde{G}}$ has a loop or multiple edges incident to $[v]_{v_1=v_3}$, or the number of odd vertices in ${\tilde{G}}$ is not two. In the former case, $v_1$ and $v_3$ are joined by a path P of length one or two in G through neither $v, v_2$ nor $v_4$. In the latter case, both $v_1$ and $v_3$ have odd degree in G, and ${\tilde{G}}$ is an even triangulation. Similarly, for the 4-contraction of v at $\{v_2,v_4\}$, we see that G has a path $P'$ of length at most two joining $v_2$ and $v_4$ in $G - \{v,v_2,v_4\}$, or both $v_2$ and $v_4$ have odd degree in G. If both P and $P'$ exist in G, then they must cross at their middle vertices, by the planarity, and hence both P and $P'$ have length exactly two.

Consequently, by symmetry, we have one of the following structures around v (see Fig. 9):

• (a) $v_2$ and $v_4$ are odd vertices, and $P=v_1v_3 \in E(G)$.

• (b) $v_2$ and $v_4$ are odd vertices, and $P=v_1xv_3$ with $x \notin \{v,v_2,v_4\}$.

• (c) $P=v_1yv_3$ and $P'=v_2yv_4$ with $y \notin \{v,v_1,v_2,v_3,v_4\}$.

Fig. 9

The structure around v: a white circle (resp., a black square) denotes an even (resp., odd) vertex, and a black circle denotes a vertex of even or odd degree

Case (a)  Since both $v_2$ and $v_4$ are odd vertices, two triangular regions $v_1v_2v_3$ and $v_1v_4v_3$ are faces by Lemma 9(i). So we have $G \simeq C_3 + \bar{K_2}$, contrary to $|V(G)|\ge 6$.

Case (b)  Let us consider the structure of the interior $I_C$ of the 4-region bounded by $C=xv_1v_2v_3$. We can apply Lemma 9(ii) to $I_C$ since all inner vertices are even. If $v_1v_3\in E(G)$, then G has the structure (a), but we note $xv_2 \notin E(G)$. (For otherwise, i.e., $xv_2 \in E(G)$, then the interior of at least one of the two regions $xv_1v_2$ and $xv_2v_3$ contains a vertex, since $v_2$ is odd. This contradicts Lemma 9(i).) If $I_C$ contains a single 4-vertex, then $v_2$ must be even, by Lemma 9(i), a contradiction. Finally, we consider the case when $I_C$ is isomorphic to $Q^{(k)}$ for some $k \ge 1$. If two adjacent 4-vertices in $Q^{(k)}$, say s and $s'$, are neighbors of $v_1$, then $v_2$ has even degree, a contradiction. On the other hand, if they are neighbors of $v_2$, then the 4-vertex s is contractible at $\{s',v_1\}$ (or $\{s',v_3\}$), a contradiction. Hence this case does not happen.

Case (c)  Let $D=yv_2v_3$ be the 3-cycle and let $I_D$ be the interior of the region bounded by D. Let $G_D$ be the subgraph of G induced by the vertices of D and those contained in $I_D$. By symmetry, we may suppose that $G_D$ contains an odd vertex of G. If $G_D$ contains two odd vertices of G, then the outer region of D contains only even vertices in G, which contradicts Lemma 9(i). Hence, by the Handshaking Lemma and Lemma 8, $I_D$ contains exactly one odd vertex of G, and other odd vertices of $G_D$ are contained in D but all of them have even degree in G.

If $I_D$ has a single vertex, then the interior of two triangular regions $yv_1v_2$ and $yv_3v_4$ must contain vertices, since $\deg _G(v_2)$ and $\deg _G(v_3)$ are even. However, this contradicts Lemma 9(i) since G is a 2-odd triangulation. Thus we may suppose that $I_D$ contains at least two vertices. Here we prove that $I_D$ contains a 4-vertex. If we let $p_i$ be the number of i-vertices in $G_D$, then we have $3p_3+2p_4+p_5 \ge 12$, by Euler’s formula, which implies that $G_D$ has at least four vertices of degree less than 6. Observe that at least two of $y, v_2$ and $v_3$ have degree at least 4 in $G_D$, and that $G_D$ contains exactly one odd vertex s in $I_D$. Hence, if no vertex in $I_D$ has degree 4, then $G_D$ has at most four vertices of degree less than 6. However, the above inequality for $G_D$ claims that if $G_D$ has exactly four vertices of degree less than 6, then all of them must have degree 3, contrary to the current situation.

Let u be a 4-vertex u in $I_D$ which can be found as above, and let $u_1u_2u_3u_4$ be the link of u in G. Since at least one neighbor of u is contained in $I_D$ and since all three vertices of D have even degree in G, the structure around u must be (c). Hence G has two paths $P_1$ and $P_2$ of length 2 which join $u_1$ and $u_3$, and $u_2$ and $u_4$ respectively, and cross at their middle vertex z. By symmetry, we may suppose that $u_2$ and $u_3$ are contained in the triangular region $u_1u_4z$. If all of the three triangular regions $u_1u_2z, u_2u_3z$ and $u_3u_4z$ have no inner vertex, then we can apply an octahedron removal to remove $u,u_2$ and $u_3$. For, if one of them, say $u_1u_2z$, contains inner vertices, then the interior of $u_1u_2z$ must have an odd vertex, and then contains a 4-vertex again by the same argument as above. This argument does not continue since G is finite.

We have shown that unless $G = C_3 + \bar{K_2}$, G admits a 4-contraction or an octahedron removal. Hence the proof completes. $\square$

Now we prove Proposition 6.

Proof of Proposition 6

Let G be a 2-odd triangulation. By Theorem 10, there exists a sequence of 2-odd triangulations $C_3 + \bar{K_2}=G_0,G_1,G_2,...,G_k=G$ such that $G_{i+1}$ is obtained from $G_i$ by a single octahedron addition or a single 4-splitting. We prove the proposition by induction on k. When $k=0$, $G = G_k = G_0 = C_3 + \bar{K_2}$ is the face subdivision of $C_3$.

If $G_{l}$ is obtained from $G_{l-1}$ by either a single octahedron addition or a single 4-splitting, then $G_{l-1}$ is a face subdivision with a unique color factor, by induction hypothesis. In the former case, $G_l$ is also a face subdivision with a unique color factor, as shown in Fig. 10. In the latter case, we have three possibilities for the structure around a vertex to which a 4-splitting is applied, as shown in Fig. 11. In any case, $G_l$ is a face subdivision with a unique color factor, and hence the proposition holds. $\square$

Fig. 10

An octahedron addition and a color factor

Fig. 11

4-Splittings and color factors

4 Lemmas and a Proof of Theorem 3

Let $L=C_3 + \bar{K_2}$, and let ${\widetilde{L}}$ be the 2-odd triangulation obtained from $C_3 + \bar{K_2}$ by a single octahedron addition (see Fig. 12).

Fig. 12

The 2-odd triangulations L and ${\widetilde{L}}$

In order to prove Theorems 3 and 4, we give two tools for induction on the number of vertices, one is to use an octahedron, and the other is to use two adjacent 4-vertices added on an edge. We first describe how an octahedron in 2-odd triangulations can be moved, and how an octahedron removal is related to 4-contractions. (We can find a similar result for even triangulations [5].)

Lemma 11

LetG be a 2-odd triangulation.

• 1. Letf and$f'$ be two faces ofG, and let$G_f$ (resp., $G_{f'}$) denote the one obtained fromG by applying an octahedron addition tof (resp., $f'$). Then$G_f$ and$G_{f'}$ areN-equivalent.

• 2. Let$G'$ denote a 2-odd triangulation obtained fromG by two octahedron additions. Then$G'$ can be reduced intoG byN-flips and 4-contractions.

Proof

• 1. Let v be a vertex of G whose degree is $k \ge 4$. Let $f_0, f_1,\ldots ,f_{k-1}$ be the faces incident to v lying around v in this cyclic order. We can see that the octahedron added in $f_1$ can moved to $f_0$ as shown in Fig. 13. (Note that the figure shows the case when $\deg (v)=6$, but the same can be done unless $\deg (v)=3$, by repeatedly applying similar N-flips.) It is easy to see that repeating the above procedures, the octahedron added in f can be moved to any face $f'$.

• 2. By the result (1), we can move two added octahedra freely in G, and hence the two octahedra can be put in two adjacent faces in G. Such two octahedra can be eliminated as shown in Fig. 14 by a single N-flip and three 4-contractions. $\square$

Fig. 13

Moving an octahedron

Fig. 14

Eliminating two octahedra by a single N-flip and three 4-contractions

By Lemma 11, we have the following proposition which follows from Theorem 10 immediately.

Proposition 12

Every 2-odd triangulation with an odd number of vertices can be reduced to L by a sequence of 4-contractions andN-flips, and one with an even number of vertices can be reduced to${\widetilde{L}}$ by the two operations.

Proof

Let G be a 2-odd triangulation. By Theorem 10, there exists a finite sequence of 2-odd triangulations $G=G_0,G_1,\ldots ,G_k=L$ such that $G_i$ is obtained from $G_{i-1}$ by either a 4-contraction or an octahedron removal, for $i=1,\ldots ,k$. Observe that the 4-contraction preserves the parity of the number of vertices but the octahedron removal does not. Hence if |V(G)| is odd (resp., even), the sequence contains an even (resp., odd) number of octahedron removals. Observe that an octahedron in a 2-odd triangulation can be moved to any face by N-flips, and that two octahedra can be eliminated by N-flips and 4-contractions, by Lemma 11. Hence, if |V(G)| is odd, then G can be reduced to L by a sequence of 4-contractions. Otherwise (i.e., if |V(G)| is even), G can be to ${\tilde{L}}$. $\square$

Secondly we deal with two adjacent 4-vertices u, v. Let G be a 2-odd triangulation and let $e=ab$ be an edge of G shared by two triangular faces abc and abd. Subdivide e by two vertices u and v to form a path auvb, and add edges uc, ud, vc and vd, as shown in Fig. 15. This operation is a 2-subdivision, and $\{u,v\}$ is a 2-subdividing pair.

Fig. 15

The 2-subdivision of ab

Lemma 13

Let G be a 2-odd triangulation and letv be a 4-vertex with link$v_1v_2v_3v_4$, where$v_1$ is even. Letu be the common neighbor of$v_1$ and$v_2$ other thanv. Suppose that the triangulationH obtained fromG by a 4-contraction ofv at$\{v_1,v_3\}$ is a 2-odd triangulation. ThenG can be transformed into the one obtained fromH by a 2-subdivision of the edge$u[v]_{v_1=v_3}$, by a sequence ofN-flips, keeping the degree of$v_2$.

Proof

Let $vv_4a_1a_2 \ ... \ a_kv_2$ be the link of $v_1$ in G, where $k \ge 4$ is an even integer and let $a_k=u$. If $\deg _G (v_1) = 4$, then $\{v_1,v\}$ can be regarded as a 2-subdividing pair lying on the edge $uv_3$ in G. Hence G is a 2-odd triangulation obtained from H by a 2-subdivision of the edge $u[v]_{v_1=v_3}$.

So we suppose that $\deg _G (v_1) \ge 6$. Apply the N-flip to the path $vv_4v_1a_1$ in G to decrease the degree of $v_1$, and let $G'$ be the resulting graph (see Fig. 16). By the assumption, $a_1, ... , a_k$ are not adjacent to $v_3$ in G. Moreover, $v_4,a_1,a_2, \ldots , a_k,v_2$ are all distinct. Hence $G'$ is simple and we see that $\deg (v_2)$ is unchanged, and that v still has degree 4. After this, repeating the N-flip to $va_iv_1a_{i+1}$ for all even $i \in \{ 2,4,...,k-3 \}$, we can transform G into a 2-odd triangulation obtained from H by a 2-subdivision of the edge $u[v]_{v_1=v_3}$, keeping $\deg (v_2)$. $\square$

Fig. 16

The N-flip of the path $vv_4v_1a_1$

Two 2-odd triangulations G and $G'$ are $NP_2$-equivalent, denoted $G \sim _{NP_2} G'$, if G and $G'$ can be transformed into each other by N- and $P_2$-flips. For a 2-odd triangulation H, let $H + \Gamma (m)$ denote a 2-odd triangulation obtained from H by repeating a 2-subdivision of an edge m times, where we note that $H+\Gamma (m)$ has $|V(H)|+2m$ vertices. Since we can move a 2-subdividing pair on edges freely by $P_2$-flips, we see that the expression $H + \Gamma (m)$ is well-defined.

Now we prove Theorem 3.

Proof of Theorem 3

By Proposition 12, if |V(G)| is even, then G can be reduced to ${\tilde{L}}$ by N-flips and 4-contractions, and hence, applying Lemma 13 repeatedly, we have $G \sim _{NP_2} {\tilde{L}}+\Gamma (m)$ (where $m =\frac{1}{2} (|V(G)|-8)$), since a 2-subdividing pair can be moved freely by $P_2$-flips. Similarly, if |V(G)| is odd, then $G \sim _{NP_2} L+\Gamma (m)$, where $m =\frac{1}{2} (|V(G)|-5)$. Therefore, if $|V(G)|=|V(G')|$, then G and $G'$ are $NP_2$-equivalent, via the standard form ${\tilde{L}}+\Gamma (m)$ or $L+\Gamma (m)$, depending on the parity of the number of vertices. $\square$

5 Proof of Theorem 4

In this section, we establish a way to transform 2-odd triangulations without $P_2$-flips. In the proof of Theorem 3, it is a key fact that a 2-subdividing pair can be moved freely by $P_2$-flips, but forbidding $P_2$-flips in Theorem 4, we carefully observe how a 2-subdividing pair can be moved only by N-flips.

Lemma 14

LetH be a 2-odd triangulation, and let$e_1,...,e_k$ be all edges incident to a vertex$v \in V(H)$ appearing in this cyclic order with respect to the rotation ofv. LetG (resp., $G'$) be the 2-odd triangulation obtained fromH by a 2-subdivision of$e_i$ (resp.,$e_{i+2}$). If$k=\deg (v) \ge 4$, thenG and $G'$ areN-equivalent.

Proof

Let $v_1v_2...v_k$ be the link of a vertex $v \in V(G)$ and we suppose $e_i=vv_i$ for each $i \in \{ 1,...,k \}$ and $k = \deg (v) \ge 4$. Suppose that G is obtained from H by a 2-subdivision of $vv_i$ with two vertices x and y to form a path $vxyv_i$. If $\deg _H(v)=4$, then x and v can be regarded as a 2-subdividing pair on $yv_{i+2}$ in G. Therefore, we have $G=G'$. So we may suppose that $\deg _H(v) \ge 5$. First apply the N-flip of the path $xv_{i+1}vv_{i+2}$, and next apply the N-flip of the path $xv_{i-1}yv_i$ (see Fig. 17). Since $v_1,...,v_k$ are all distinct in G and $k \ge 5$, each N-flip preserves the simpleness. Hence G can be transformed into $G'$ by N-flips. $\square$

Fig. 17

Moving a 2-subdividing pair

In Lemma 14, we say that $e_i$ and $e_{i+2}$ are alternate edges incident to v. Lemma 14 tells us that a 2-subdividing pair on an edge e can be moved to an alternate edge of e incident to the same vertex. However, we note that the condition “$\deg (v) \ge 4$” is necessary in Lemma 14. Hence, in order to move a 2-subdividing pair freely, we introduce the notion of “flexibility” of a 2-odd triangulation, as follows.

Two edges e and $e'$ in a triangulation are equivalent if there exists a sequence of edges $e_1,\ldots ,e_m$ of G with $e=e_1$ and $e'=e_m$ such that for $i=1,\ldots ,m-1$, $e_i$ and $e_{i+1}$ are alternate edges incident to the same vertex of degree at least 4 in G. We call such a sequence of edges an alternate sequence between e and $e'$.

Let G be a 2-odd triangulation. Let $G_1$ (resp., $G_2$) be the 2-odd triangulation obtained from G by a 2-subdivision of $e_1$ (resp., $e_2$). By Lemma 14, $G_1$ and $G_2$ are N-equivalent if $e_1$ and $e_2$ are equivalent in G. It is easy to see the following hold;

• a frame edge and a spoke in G are not equivalent, and

• any two frame edges of G are equivalent (since every frame edge joins two vertices of even degree at least 4, and since frame edges incident to the same vertex appear alternately in the rotation around the vertex).

We say that a 2-odd triangulation G is flexible if any two spokes of G are equivalent. We give a characterization of flexible 2-odd triangulations, as in the following.

Theorem 15

LetG be a 2-odd triangulation, and letx and$x'$ be the two odd vertices. ThenG is flexible if and only if at least one of the following two conditions holds:

• (i) At least one ofx and$x'$ is of degree at least five.

• (ii) If bothx and$x'$ have degree three, thenx and$x'$ have at most one common neighbor.

Proof

If x is an odd vertex of degree at least five, then all spokes incident to x are equivalent in G, since two alternate spokes are equivalent, by Lemma 14. It is easy to see that any spoke is equivalent to some spoke incident to x, since we can find an alternate sequence between them. Consequently, any two spokes of G are equivalent, via the spokes incident to x. So it suffices to prove the following:

A 2-odd triangulation G with two 3-vertices x and $x'$ is flexible if and only if x and $x'$ have at most one common neighbor.

Let H be the frame of G, which can uniquely be taken by Proposition 6. Then H has two triangular faces $X=abc$ and $X'=a'b'c'$, which have x and $x'$ in the interior in G, respectively. Let R be the subgraph of H induced by all edges on the boundary cycle of an even face of H. That is, $R=H-D$, where $D=E(X) \cap E(X')$ which might be empty.

(“Only if” part.) Suppose that X and $X'$ share at least two vertices, say $a=a'$ and $b=b'$. If $c =c'$, then $G=C_3+{\bar{K}}_2$, in which $\{ax,ax'\}$, $\{bx,bx'\}$ and $\{cx,cx'\}$ are three equivalence classes of spokes, and we are done. Hence we may suppose that $c \ne c'$. Then $R=H-ab$, which is a bipartite plane graph with a facial cycle $acbc'$ since each face of R is even. We color the vertices of R black and white, according to the bipartition of R, so that a and c are black and white, respectively. Observe that a spoke e is equivalent to xa in G if and only if e is incident to a black vertex. Hence xa and xc are not equivalent since xc is incident to a white vertex.

(“If” part.) Suppose that two 3-cycles X and $X'$ share at most one vertex in H. Then $R=H$ since $D=E(X) \cap E(X') = \emptyset$. Since H is connected, X and $X'$ are connected in H by a path P. Taking P to be shortest, we let $P=p_1 \ldots p_m$ with $p_1=a$ and $p_m=a'$, in which each $p_i$ with $i \in \{2,\ldots ,m-1\}$ is supposed to be contained in neither X nor $X'$, where we might have $a=a'$, i.e., $m=1$. Cutting R along P and making a copy ${\tilde{P}}=\tilde{p_1} \ldots {\tilde{p}}_m$ of P, we obtain the plane graph, say $R'$, whose boundary cycle is $p_1bc \tilde{p_1} \ldots \tilde{p_m} c'b'p_m \ldots p_1$. Then $R'$ is bipartite since each face of $R'$ is even. In the bipartition of $R'$, $p_1$ and c have the same color, say black, and $\tilde{p_1}$ and b are white.

Observe that if e and $e'$ are two spokes in G incident to vertices of $R'$ with the same color, say black, then we can find an alternate sequence of edges in $R'$ between e and $e'$ without crossing P, in which every edge in the sequence is incident to a black vertex of $R'$. On the other hand, if e and $e'$ are incident to vertices in $R'$ with distinct colors, then we can take two alternate sequences in G through faces in $R'$ from e to some edge incident to $p_i$, and from $e'$ to an edge incident to $\tilde{p_i}$ for some i, since they form a single alternate sequence of edges in G between e and $e'$ which crosses P exactly once in G. In the sequence, we should note that $p_i$ and $\tilde{p_i}$ are the same vertex in R, but they are distinct vertices in $R'$ with distinct colors. So any two spokes are equivalent in G. $\square$

Consider three 2-odd triangulations $L_9, L_s$ and $L_f$ shown in Fig. 18. We note that $L_s$ and $L_f$ are obtained from $L=C_3+{\bar{K}}_2$ by 2-subdividing a spoke and a frame edge, respectively, and that $L_9$ is a flexible 2-odd triangulation obtained from $L_s$ by 2-subdividing a spoke. For a triangulation G and an octahedron O which is an induced subgraph of G, $G-O$ denotes a triangulation obtained from G by an octahedron removal which removes the three 4-vertices of O.

Fig. 18

The 2-odd triangulations $L_9$, $L_s$ and $L_f$

Lemma 16

Every flexible 2-odd triangulationG with$k \ge 9$ vertices can be reduced to a flexible 2-odd triangulation with$k-2$ vertices byN-flips and a single 4-contraction, preserving the flexibility, unlessG is isomorphic to$L_9$.

Proof

Let T be a flexible 2-odd triangulation. Let $T'$ (resp., $T''$) be any 2-odd triangulation obtained from T by a single 4-splitting (resp., octahedron addition). We first observe that $T'$ and $T''$ are flexible, by the characterization of flexible 2-odd triangulations (Theorem 15). Moreover, moving the octahedron in $T''$ to another face of T by N-flips (Lemma 11(1)), we see that all 2-odd triangulations in the process are flexible.

We first establish the following claim.

Claim. By several N-flips, G can be transformed into a flexible 2-odd triangulation which admits a 4-contraction, preserving the flexibility.

Proof of the Claim. By Theorem 10, G has a 4-contractible 4-vertex (i.e., one to which a 4-contraction can be applied) or a removable octahedron O. If we have the former, then the claim holds with no N-flip. Hence suppose the latter, and let $G'=G-O$. Since $|V(G)| \ge 9$, $G'$ still has a 4-contractible 4-vertex v or a removable octahedron $O'$, by Theorem 10 again.

If $G'$ is flexible, then O can be moved freely in $G'$ by N-flips, preserving the flexibility as mentioned in the first paragraph. So if $G'$ has v, then v is a required 4-contractible 4-vertex in G with O moved somewhere. On the other hand, if $G'$ has $O'$, then let $G''=G'-O'$. If $G''$ is flexible, then moving O and $O'$ suitably in $G'$, we can eliminate them using N-flips and 4-contractions by Lemma 11(2), preserving the flexibility. The case when $G''$ is not flexible will be considered in the next case, since O and $O'$ may be dealt with equally in $G''$.

If $G'$ is not flexible, then by Theorem 15, $G'$ has two 3-vertices x and $x'$ with neighbor a, b, c and $a',b',c'$, respectively, with $a=a'$ and $b=b'$, where we note $c \ne c'$ since $|V(G')| \ge 6$. Observe that O is contained in one of the six 3-regions incident to x or $x'$ in G. If $G'$ has a 4-contractible 4-vertex v which is also 4-contractible in G, then we are done. Hence we may suppose that $v=c$ and O is put in the face xbc in $G'$. (For, since $\deg _{G'}(a) \ge 5$ and $\deg _{G'}(b) \ge 5$, v coincides with neither a nor b.) In this case, we can move O in G to the face $x'ab$ by two N-flips, keeping at least one of $\deg (x) \ge 5$ and $\deg (x') \ge 5$, and after that, we can apply a 4-contraction of $v=c$, preserving the flexibility. If $G'$ has the octahedron $O'$, then $O'$ is incident to neither x nor $x'$, since $G'$ is not flexible. In this case, we can move $O'$ in G to a face neighboring to the 3-region including O, and apply the procedures in Lemma 11(2). Then we can apply a single 4-contraction after an N-flip, keeping at least one of $\deg (x) \ge 5$ and $\deg (x') \ge 5$. $\square$

By the claim, we may suppose that G has a 4-contractible 4-vertex v with link $v_1v_2v_3v_4$, and let $G'$ be the resulting graph by the 4-contraction at $\{v_1,v_3\}$. If $G'$ is flexible, then the 4-contraction is a required one, and hence we suppose that $G'$ is not flexible. By Theorem 15, $G'$ has two 3-vertices x and $x'$ with neighbors a, b, c and $a',b',c'$, respectively, with $a=a'$ and $b=b'$, where we note $c \ne c'$ since $|V(G')| \ge 7$.

We first suppose that $\deg _G(x) \ge 5$ or $\deg _G(x') \ge 5$, and that they decrease to 3 by the 4-contraction of v in $G'$. Then we may suppose that $v_2=x$ in $G'$ by symmetry. That is, $v_2$ has degree 5 in G with link $v_1vv_3bc$, and by the 4-contraction of v at $\{v_1,v_3\}$, the link of $v_2$ is deformed into $bc[v]_{v_1=v_3}$ in $G'$. (Since the case when the link of $v_2$ is $v_1vv_3ab$ can be similarly proved, we prove only the case when it is $v_1vv_3bc$.) By Lemma 13, G can be transformed into $G'$ with a 2-subdivision of the edge $c[v]_{v_1=v_3}$ by N-flips, keeping $\deg (v_2)=5$, and hence preserving the flexibility, by Theorem 15. Moreover, the 2-subdividing pair on the link of x or $x'$ can be moved to the edge ab by two N-flips, keeping at least one of $\deg (x) \ge 5$ and $\deg (x') \ge 5$. By Theorem 10, $G'$ can still be reduced by a sequence of 4-contractions and octahedron removals, since $|V(G')| \ge 7$. These reductions in $G'$ must be done in the 4-region $xax'b$ containing c and $c'$, since no face incident to ab is eliminated in $G'$. (Note that a or b may be identified to another vertex in the sequence of the above reductions. Even if this occurs, then we keep the 4-region $xax'b$ with this labeling.) Hence all graphs arisen in the process must be flexible, since both x and $x'$ always have degree five. (If the sequence contains two octahedron removals, then we apply Lemma 11(2). If the sequence contains a single octahedron removal but no 4-contraction, then $G'={\tilde{L}}$, contrary to $G'$ being non-flexible.)

Fig. 19

Structures around v

If G has two 3-vertices x and $x'$ sharing at most one common neighbor, but they have at least two common neighbors in $G'$ by the 4-contraction of v. We may let $pb'qb$ be the link of v in G, and suppose that the 4-contraction of v at $\{b,b'\}$ transforms G into $G'$, where p is contained in the interior of the 4-region bounded by $abvb'$ in G. (See the left-hand of Fig. 19.) Since the 4-contraction of v at $\{b,b'\}$ is applicable in G, we have $a=a'=p$. If the 4-contraction of v at $\{p,q\}$ is applicable in G, then the two 3-vertices x and $x'$ share only one neighbor $a=a'$ in the resulting graph, which is a required flexible 2-odd triangulation with fewer vertices, by Theorem 15. Hence we prove that if the 4-contraction of v at $\{p,q\}$ is not applicable, then G is isomorphic to $L_9$, as follows.

We first suppose that q coincides with $c'$ or c, say the former by symmetry. Then apply Lemma 9(ii) to the 4-region $ac'bc$. (If we have an octahedron removal for reducing the 4-region, then we move the octahedron to a face xbc. Then the 4-contraction of v at $\{b,b'\}$ is applicable preserving the flexibility, since x has degree five in the current graph. So we may suppose that any 4-region can be reduced only by 4-contractions. This trick will be used in this proof several times.) Since the 4-region acbc is bounded by only frame edges, the 4-region must have exactly one vertex, as in the right-hand of Fig. 19. Then the graph is isomorphic to $L_9$. (If the region $ac'bc$ is isomorphic to $Q^{(m)}$ for some $m\ge 1$, then at least one of a and c has odd degree, a contradiction.)

Hence G has the 6-region D bounded by a cycle $C=qb'c'pcb$. Since all edges of C are frame edges, the frame edges divide the interior of C into regions bounded by an even cycle. If D has a chord of C which must be a frame edge, then only an admissible chord is pq, as in the center of Fig. 19, since other chords are not obstructions of the 4-contraction of v at $\{p,q\}$. In this case, apply Lemma 9(ii) to two 4-regions $pqb'c'$ and pcbq. Similarly to the above case, each of two 4-regions must have exactly one vertex, and hence, we can apply the 4-contraction of the 4-vertex in $pqb'c'$ at $\{c',q\}$ keeping $c\ne c'$, contrary to the resulting graph being non-flexible.

Finally we consider the case when D has no chord. If D contains exactly one inner vertex u, then u has degree 6 and is adjacent to all vertices of C. So, applying the 4-contraction of $c'$ at $\{x',u\}$, we have a flexible 2-odd triangulation with fewer vertices, a contradiction. Thus, we may suppose that D contains at least two vertices. By the result in [2, Theorem 3.1], we know that the number of vertices of degree at least 6 in a 6-region is at most 1 if all vertices in the region are of degree at least 6, and hence D contains an inner 4-vertex u with link $L_u=u_1u_2u_3u_4$. By the minimality of G with respect to the flexibility, the 4-contraction of u at $\{u_1,u_3\}$ and that at $\{u_2,u_4\}$ are not applicable, and so there are two 3- or 4-cycles passing through $u_1uu_3$ and $u_2uu_4$. By a similar argument in the proof of Theorem 10 and the assumption for octahedra in D, at least one of $u_1,u_3$, and at least one of $u_2, u_4$, say $u_1$ and $u_2$ by symmetry, are contained in C. Since D has no chord, then $u_1u_2$ coincides with an edge of C. Moreover, by the same reason, we may suppose that $u_3$ is an inner vertex of D. Observe that if $u_4$ is also inner vertex in D, then $u_4$ has degree at least 6. (For otherwise, a 4-contraction of u at $\{u_2,u_4\}$ is possible.) Since D can have a diagonal, a 4-contraction of u at $\{u_1,u_3\}$ is always possible in D, a contradiction. $\square$

Let G be a 2-odd triangulation and let H be the frame of G. Consider an N-flip of a 3-path $P=abcd$ connecting two vertices a and d of the color factor of G. Then the edge bc must be contained in H. If we let $a_1 \ldots a_m cb$ and $bc d_1 \ldots d_l$ be the links of a and d in G in the same cyclic order, then the N-flip of P in G corresponds to a generalized diagonal flip of the edge bc in H to replace it with $a_1d_1$ in the 2-cell region of H bounded by $ba_1\ldots a_m c d_1 \ldots d_l$, as shown in the left-hand of Fig. 20. (Observe that any generalized diagonal flip preserves the size of faces of H, and hence, the number of odd faces of H is always preserved in the process of generalized diagonal flips.) This interpretation will be useful in the following lemma.

Fig. 20

Generalized diagonal flips in the frame H

Lemma 17

LetG be a non-flexible 2-odd triangulation with$|V(G)| \ge 9$. ThenG can be transformed into a flexible 2-odd triangulation by a sequence ofN-flips.

Proof

Let H be the frame of G. Since $|V(G)| \ge 9$, we have $H \ne C_3$. By Theorem 15, G has two 3-vertices x and $x'$ sharing two common neighbors. Hence H has two triangular faces abc and $abc'$ sharing the edge ab. Let D be the 4-region bounded by $C=acbc'$ not containing the two triangular faces. Since $|V(G)| \ge 9$, the interior of D has at least one edge of H.

First suppose that $\deg _H(c) \ge 3$ or $\deg _H(c') \ge 3$, say the former. Let $c'' \ne a$ be the neighbor of c in H which is consecutive to b with respect to the rotation of c. (Note that $c' \ne c''$ since otherwise at least three 3-regions in H, which means that at least three odd vertices, a contradiction.) Then we can apply a generalized diagonal flip of bc to $ac''$ in H, as shown in the right-hand of Fig. 20. The resulting plane graph, denoted by $H'$, has exactly two triangular faces $abc'$ and $acc''$. By Theorem 15, the face subdivision of $H'$ is flexible.

Secondly we suppose that $\deg _H(c) = \deg _H(c') =2$. Since D has an inner edge, we have $\deg _H(a) \ge 4$ and $\deg _H(b) \ge 4$. Now apply a generalized diagonal flip of ab to $cc'$. The resulting graph can be dealt as the one in the previous case. $\square$

Let K be a flexible 2-odd triangulation, and let $K+(s,t)$ denote a 2-odd triangulation obtained from K by 2-subdivisions of spokes s times and frame edges t times, respectively, where $s,t\ge 0$ and $K=K+(0,0)$. Since K is flexible, every 2-subdividing pair added on a spoke can be moved to any spoke, and so can be any 2-subdividing pair on a frame edge. Therefore, the notation $K+(s,t)$ is well-defined, that is, any two graphs expressed by $K+(s,t)$ are N-equivalent for any $s,t \ge 0$. In Lemma 13, if G is transformed into $G'$ by a single 4-contraction so that $|U(G)|=|U(G')|+1$, then $G \sim _N K+(1,0)$. On the other hand, if $|U(G)|=|U(G')|$, then $G \sim _N K+(0,1)$. Therefore, if G can be reduced to K by a sequence of N-flips and 4-contractions, preserving the flexibility, we have $G \sim _N K+(s,t)$ by applying Lemma 13 repeatedly, where $s=|U(G)|-|U(K)|$ and $2(s+t)=|V(G)|-|V(K)|$. This fact plays an important role for our inductive argument in the following proof.

Proof of Theorem 4

Let G and $G'$ be 2-odd triangulations with $|V(G)|=|V(G')|$ and $|U(G)|=|U(G')|$. By Theorem 10, if $|V(G)|=5$, then $G=L$. If $|V(G)|=7$, then G is either $L_s$ or $L_f$, which can be distinguished by |U(G)|. If $|V(G)|=8$, then G is isomorphic to ${\tilde{L}}$. Hence suppose $|V(G)|=|V(G')|\ge 9$. If G or $G'$ is not flexible, then we can apply Lemma 17 to transform it to a flexible one. So we may suppose that both G and $G'$ are flexible.

If |V(G)| is even, then both G and $G'$ can be reduced to ${\widetilde{L}}$ by N-flips and 4-contractions, preserving the flexibility, by Lemma 16. Since $|V(G)|=|V(G')|$ and $|U(G)|=|U(G')|$, we have $G \sim _N {\widetilde{L}}+(s,t) \sim _N G'$, where $s=|U(G)|-3$ and $t=\frac{1}{2}(|V(G)|-8)-s$.

Suppose that |V(G)| is odd. Applying 4-contractions and N-flips to G, we obtain a minimal flexible 2-odd triangulation H, preserving the flexibility. By Lemma 16, H is either $L_f$ or $L_9$. Observe that there exist exactly two 2-odd triangulations $L_f$ and $L_s$ with seven vertices, but $L_s$ is not flexible. If both G and $G'$ can be reduced to either of $L_f$ and $L_9$ by 4-contractions and N-flips, then G and $G'$ are N-equivalent, via the form $L_f+(s,t)$ or $L_9+(s,t)$, since $L_f$ and $L_9$ are flexible. So suppose that G is reduced to $L_f$, but $G'$ is to $L_9$. In this case, we have $G \sim _N L_f+(s,t)$ and $G' \sim _N L_9 + (s',t')$, by Lemma 13. Note that $s=s'+2 \ge 2$ and $t'=t+1 \ge 1$, since $|V(L_f)|=7$, $|U(L_f)|=2$, $|V(L_9)|=9$ and $|U(L_9)|=4$. Seeing that $L_f+(2,0) \sim _N L_9+(0,1)$ by Fig. 21, we have

$$\begin{aligned}&G \sim _N L_f+(s,t) \sim _N (L_f + (2,0))+(s-2,t) \sim _N (L_9+(0,1)) + (s',t'-1)\\&\quad \sim _N L_9+(s',t') \sim _N G'. \end{aligned}$$

This completes the proof of Theorem 4. $\square$

Fig. 21

$L_f+(2,0) \sim _N L_9+(0,1)$