text:
# Reducing Dehn fillings and small surfaces

## 1. Introduction

Let $`M`$ be a compact, connected, orientable $`3`$-manifold with a torus boundary component $`_0M`$. Let $`\gamma `$ be a slope on $`_0M`$, that is, the isotopy class of an essential simple closed curve on $`_0M`$. The $`3`$-manifold obtained from $`M`$ by $`\gamma `$-Dehn filling is defined to be $`M(\gamma )=MV_\gamma `$, where $`V_\gamma `$ is a solid torus glued to $`M`$ along $`_0M`$ in such a way that $`\gamma `$ bounds a meridian disk in $`V_\gamma `$.

By a small surface we mean one with non-negative Euler characteristic including non-orientable surfaces. Such surfaces play a special role in the theory of $`3`$-dimensional manifolds. Thurston’s geometrization theorem for Haken manifolds \[Th\] asserts that a hyperbolic $`3`$-manifold $`M`$ with non-empty boundary contains no essential small surfaces. Furthermore, if $`M`$ is hyperbolic, then the Dehn filling $`M(\gamma )`$ is also hyperbolic for all but finitely many slopes \[Th\], and a good deal of attention has been directed towards obtaining a more precise quantification of this statement.

Let us say that a $`3`$-manifold is of type $`𝒮`$, $`𝒟`$, $`𝒜`$, or $`𝒯`$, if it contains an essential orientable small surface which is an essential sphere, disk, annulus or torus, and of type $`𝒫`$, $``$, or $`𝒦`$, if it contains a non-orientable small surface which is a projective plane, Möbius band or Klein bottle, respectively. Especially $`3`$-manifolds of type $`𝒮`$, $`𝒟`$, $`𝒜`$ and $`𝒯`$ are called reducible, $``$-reducible, annular and toroidal, respectively. The distance $`\mathrm{\Delta }(\gamma _1,\gamma _2)`$ between two slopes on a torus is their minimal geometric intersection number. The bound $`\mathrm{\Delta }(X_1,X_2)`$ is the least nonnegative number $`m`$ such that if $`M`$ is a hyperbolic manifold which admits two Dehn fillings $`M(\gamma _1)`$, $`M(\gamma _2)`$ of type $`X_1`$, $`X_2`$, respectively, then $`\mathrm{\Delta }(\gamma _1,\gamma _2)m`$. Surveys of the known bounds of various choices $`(X_1,X_2)`$ and the maximal values realized by known examples are given in \[G2, W3, EW\].

In this paper we consider $`M(\gamma _i)`$, $`i=1,2`$ of only the six types $`𝒮`$, $`𝒫`$, $`𝒜`$, $``$, $`𝒯`$, or $`𝒦`$. Suppose that $`M(\gamma _i)`$ contains such a small surface $`\widehat{F}_i`$. Then we may assume that $`\widehat{F}_i`$ meets the attached solid torus $`V_{\gamma _i}`$ in a finite collection of meridian disks, and is chosen so that the number of disks $`n_i`$ is minimal among all such surfaces in $`M(\gamma _i)`$. The main results of this paper are the followings.

###### Theorem 1.1.

Suppose that $`M`$ is hyperbolic. If $`M(\gamma _1)`$ and $`M(\gamma _2)`$ are of type $`𝒮`$ or $`𝒫`$, then $`\mathrm{\Delta }(\gamma _1,\gamma _2)1`$.

The original proof of the case $`(𝒮,𝒮)`$ is very complicated \[GL1\]. Our proof is remarkably short, although it is based on the analysis of intersections of two surfaces as well as \[GL1\]. Recently, Hoffman and Matignon \[HoM\] also gives such a short proof in the almost same line, but ours is still simpler than it.

If a $`3`$-manifold contains a projective plane, then it is either a reducible manifold or the $`3`$-dimensional projective space. Hence type $`𝒫`$ breaks down into type $`𝒮`$ and CYC, which means the class of manifolds with finite cyclic fundamental groups. References are: \[BZ2\] for $`\mathrm{\Delta }(𝒮,\text{CYC})=1`$; \[CGLS\] for $`\mathrm{\Delta }(\text{CYC},\text{CYC})=1`$. See also \[M, Te\] for $`\mathrm{\Delta }(𝒫,𝒫)=1`$.

###### Theorem 1.2.

Suppose that $`M`$ is hyperbolic. If $`M(\gamma _1)`$ is of type $`𝒮`$ or $`𝒫`$, and $`M(\gamma _2)`$ is of type $`𝒜`$ or $``$, then either $`\mathrm{\Delta }(\gamma _1,\gamma _2)1`$, or $`\mathrm{\Delta }(\gamma _1,\gamma _2)=2`$ with $`n_2=2`$ when $`M(\gamma _2)`$ is of type $`𝒜`$ (or $`n_2=1`$ when of type $``$).

For the case $`(𝒮,𝒜)`$, Wu \[W3\] showed that $`\mathrm{\Delta }(𝒮,𝒜)=2`$ by using the sutured manifold theory, and he asked whether $`n_2=2`$ when $`M(\gamma _1)`$ is of type $`𝒮`$ and $`M(\gamma _2)`$ is of type $`𝒜`$ with $`\mathrm{\Delta }(\gamma _1,\gamma _2)=2`$ \[W3, Question 5.8\]. Our Theorem 1.2 gives the affirmative answer of this question. Note that type $``$ breaks down into types $`𝒮`$, $`𝒜`$ and $`𝒟`$.

###### Theorem 1.3.

Suppose that $`M`$ is hyperbolic. If $`M(\gamma _1)`$ is of type $`𝒮`$ or $`𝒫`$, and $`M(\gamma _2)`$ is of type $`𝒯`$ or $`𝒦`$, then either $`\mathrm{\Delta }(\gamma _1,\gamma _2)2`$, or $`\mathrm{\Delta }(\gamma _1,\gamma _2)=3`$ with $`n_2=2`$ when $`M(\gamma _2)`$ is of type $`𝒯`$ (or $`n_2=1`$ when of type $`𝒦`$).

For the case $`(𝒮,𝒯)`$, Oh \[O\] and Wu \[W2\] independently showed that $`\mathrm{\Delta }(𝒮,𝒯)=3`$. (See also \[LOT\] for its short proof.) Hence Theorem 1.3 gives an improvement of this result. In \[JLOT\], we have showed the conclusions for two cases $`(𝒫,𝒯)`$ and $`(𝒫,𝒦)`$.

If a $`3`$-manifold is of type $`𝒦`$, then it is of type $`𝒮`$, $`𝒯`$ or a Seifert fibered manifold with finite fundamental group (a prism manifold). Indeed, non-orientable cases are necessary to prove orientable cases in our arguments. Such phenomenon is also observed in \[GL2\] and \[GL3\].

We should emphasize that all 11 cases can be treated in a unified argument in this paper. (Also, we have a plan to continue the study for the remaining pairs of $`𝒮,𝒫,𝒟,𝒜,,𝒯,𝒦`$.) Our main tool in this paper is a two-cornered cycle, which was introduced by Hoffman \[H\]. Hoffman showed that the disk bounded by a great $`x`$-cycle contains a pair of specific two-cornered cycles, called a seemly pair, and it can be used to find a new essential sphere and projective plane meeting the attached solid torus in a fewer times than an original surface, leading to a contradiction. We define a slight generalization of a great $`x`$-cycle, called an $`x`$-face, and show that it contains a seemly pair by a simpler argument than that in \[H\] and that such a pair is useful for the types $`𝒜`$ and $``$ as well.

By virtue of Theorem 1.1 and the fact $`\mathrm{\Delta }(𝒮,𝒟)=0`$ \[S\] (and hence $`\mathrm{\Delta }(𝒫,𝒟)=0`$), we can put the following assumption throughout the paper to simplify the arguments greatly:

Assumption. If $`M(\gamma _i)`$ is of type $`𝒜,,𝒯`$ or $`𝒦`$, then we assume that $`M(\gamma _i)`$ is neither of type $`𝒮`$ nor of type $`𝒟`$.

## 2. Graphs of surface intersections

Hereafter $`M`$ is a hyperbolic $`3`$-manifold with a torus boundary component $`_0M`$. An orientable surface properly embedded in $`M`$ is called essential if it is either (i) incompressible, not boundary parallel and not a sphere, or (ii) a sphere which does not bound a $`3`$-ball. Note that any essential small surface is also boundary incompressible by our assumption in Section 1. In this section we describe how (essential) small surfaces $`\widehat{F}_1`$ and $`\widehat{F}_2`$, in $`M(\gamma _1)`$ and $`M(\gamma _2)`$ respectively, give rise to labelled intersection graphs $`G_i\widehat{F}_i`$ for $`i=1,2`$ in a general context.

As in Section 1, let $`\widehat{F}_i`$ be a small surface in $`M(\gamma _i)`$ with $`n_i=|\widehat{F}_iV_{\gamma _i}|`$ minimal. (Recall that if $`\widehat{F}_i`$ is orientable then it is assumed to be essential.) Then $`n_i>0`$. Thus $`F_i=\widehat{F}_iM`$ is a punctured surface properly embedded in $`M`$, each of whose $`n_i`$ boundary components has slope $`\gamma _i`$ on $`_0M`$.

###### Lemma 2.1.

For each of six types, $`F_i`$ is incompressible and boundary incompressible in $`M`$.

###### Proof.

For types $`𝒮`$, $`𝒜`$ and $`𝒯`$, the minimality of $`n_i`$ guarantees that $`F_i`$ is incompressible and boundary incompressible in $`M`$.

For type $`𝒫`$, assume that $`D`$ is a compressing disk for $`F_i`$. Since $`D`$ is orientation-preserving on $`F_i`$, $`D`$ bounds a disk $`D^{}`$ on $`\widehat{F}_i`$. Since $`\mathrm{Int}D^{}`$ meets $`V_{\gamma _i}`$, we can create a new projective plane by replacing $`D^{}`$ with $`D`$, which meets $`V_{\gamma _i}`$ fewer than $`\widehat{F}_i`$, contradicting the minimality of $`n_i`$. Next, assume that $`E`$ is a boundary compressing disk for $`F_i`$ with $`E=ab`$, where $`a`$ is an essential arc in $`F_i`$ and $`b`$ lies in $`_0M`$. If $`a`$ joins distinct components of $`F_i`$, then a compressing disk for $`F_i`$ is obtained from two parallel copies of $`E`$ and the disk obtained by removing a neighborhood of $`b`$ from the annulus in $`_0M`$ cobounded by those components of $`F_i`$ meeting $`a`$. Hence both endpoints of $`a`$ lie in the same component, say $`_1F_i`$, of $`F_i`$. If $`n_i2`$, then $`b`$ bounds a disk $`D^{}`$ in $`_0M`$ together with a subarc of $`_1F_i`$. Then $`ED^{}`$ gives a compressing disk for $`F_i`$ in $`M`$. Therefore $`n_i=1`$. Then $`M`$ would contain a Möbius band, a contradiction.

For type $``$, assume that $`D`$ is a compressing disk for $`F_i`$. If $`D`$, which is orientation-preserving on $`F_i`$, bounds a disk $`D^{}`$ on $`\widehat{F}_i`$, a new Möbius band obtained by replacing $`D^{}`$ with $`D`$ has fewer $`n_i`$, a contradiction. Thus $`D`$ is essential, and indeed separating on $`\widehat{F}_i`$. Compressing $`\widehat{F}_i`$ along $`D`$ would give in $`M(\gamma _i)`$ a projective plane $`Q_1`$ and a disk $`Q_2`$ which are disjoint. Note that the core of $`V_{\gamma _i}`$ must meet both $`Q_1`$ and $`Q_2`$ because $`M`$ is hyperbolic. Let $`\mathrm{}`$ be a subarc of the core of $`V_{\gamma _i}`$ which connects $`Q_1`$ and $`Q_2`$, meeting them only on its endpoints. Attaching a tube along $`\mathrm{}`$ to $`Q_1Q_2`$ gives a Möbius band in $`M(\gamma _i)`$ which intersects the core of $`V_{\gamma _i}`$ in $`n_i2`$ points, a contradiction. Thus we have shown that $`F_i`$ is incompressible. The incompressibility of $`F_i`$ then implies the boundary incompressibility of $`F_i`$; otherwise, $`n_i=1`$ as previous, and furthermore a booundary-compressing disk $`E`$ allows us to isotope the core of $`V_{\gamma _i}`$ into $`\widehat{F}_i`$ as an orientation-reversing loop. Then $`M`$ would contain an essential annulus, a contradiction.

For type $`𝒦`$, assume that $`D`$ is a compressing disk for $`F_i`$. As previous, $`D`$ is orientation-preserving and essential on $`\widehat{F}_i`$. Compressing $`\widehat{F}_i`$ along $`D`$ would give in $`M(\gamma _i)`$ either a non-separating 2-sphere or two disjoint projective planes, according as $`D`$ is non-separating or separating on $`\widehat{F}_i`$. But this contradicts the irreducibility of $`M(\gamma _i)`$. The incompressibility of $`F_i`$ then implies the boundary incompressibility of $`F_i`$, unless $`M`$ contains a Möbius band, as above. ∎

We use $`i`$ and $`j`$ to denote $`1`$ or $`2`$, with the convention that, when both appear, $`\{i,j\}=\{1,2\}`$.

By an isotopy of $`F_1`$, say, we may assume that $`F_1`$ intersects $`F_2`$ transversely. By Lemma 2.1 it can be assumed that no circle component of $`F_1F_2`$ bounds a disk in $`F_1`$ or $`F_2`$. Let $`G_i`$ be the graph in $`\widehat{F}_i`$ obtained by taking as the (fat) vertices the disks $`\widehat{F}_i\mathrm{Int}F_i`$ and as edges the arc components of $`F_iF_j`$ in $`\widehat{F}_i`$. Thus the interior of any disk face of $`G_i`$ is disjoint from $`F_j`$. We number the components of $`F_i_0M`$ as $`1,2,\mathrm{},n_i`$ in the order in which they appear on $`_0M`$. On occasion we will use $`0`$ instead of $`n_i`$ in short. This gives a numbering of the vertices of $`G_i`$. Furthermore it induces a labelling of the endpoints of edges in $`G_j`$ in the usual way (see \[CGLS\]). Note that $`G_1`$ and $`G_2`$ have no trivial loops by Lemma 2.1. For the sake of simplicity we will say that $`F_i`$ and $`G_i`$ are of type $`X`$ if $`M(\gamma _i)`$ is of type $`X`$.

Since $`M`$ is hyperbolic, we have the following easy lemma.

###### Lemma 2.2.

$`n_i3`$ for $`G_i`$ of type $`𝒮`$, and $`n_i2`$ for $`G_i`$ of type $`𝒫`$.

Although $`F_i`$ of type $`𝒫`$, $``$ or $`𝒦`$ is non-orientable, we can establish a parity rule, which plays a crucial role. In fact, this is a natural generalization of the usual parity rule \[CGLS\]. First, orient all components of $`F_i`$ so that they are mutually homologous on $`_0M`$. Let $`e`$ be an edge of $`G_i`$. Since $`e`$ is an arc properly embedded in $`F_i`$, a regular neighborhood $`D`$ of $`e`$ in $`F_i`$ is a disk in $`F_i`$. Then $`D=abcd`$, where $`a`$ and $`c`$ are arcs in $`F_i`$ with induced orientations from $`F_i`$. If $`a`$ and $`c`$ are directed along $`D`$, then $`e`$ is called positive, otherwise negative. See Figure 1. Then we have the parity rule: an edge $`e`$ is positive in $`G_i`$ if and only if $`e`$ is negative in $`G_j`$.

The rest of this section will be devoted to several definitions and well known lemmas. Let $`x`$ be a label of $`G_i`$. An $`x`$-edge in $`G_i`$ is an edge with label $`x`$ at one endpoint, and an $`xy`$-edge is an edge with label $`x`$ and $`y`$ at both endpoints. If an $`x`$-edge has an endpoint at a vertex $`v`$ with label $`x`$, then it is called an $`x`$-edge at $`v`$. Especially, a positive $`xx`$-edge is called a level $`x`$-edge, which means that the vertex $`x`$ of the other graph $`G_j`$ is incident to a negative loop. In particular, $`G_i`$ does not contain a level $`x`$-edge unless $`G_j`$ is of type $`𝒫`$, $``$ or $`𝒦`$.

An $`x`$-cycle is a cycle of positive $`x`$-edges of $`G_i`$ which can be oriented so that the head of each edge has label $`x`$. A Scharlemann cycle is an $`x`$-cycle that bounds a disk face of $`G_i`$, only when $`n_j2`$. Each edge of a Scharlemann cycle has the same label pair $`\{x,x+1\}`$, so we refer to such a Scharlemann cycle as an $`(x,x+1)`$-Scharlemann cycle. The number of edges in a Scharlemann cycle is called its length. In particular, a Scharlemann cycle of length two is called an $`S`$-cycle in short.

Suppose that a Scharlemann cycle $`\sigma `$ is immediately surrounded by a cycle $`\kappa `$, that is, each edge of $`\kappa `$ is immediately parallel to an edge of $`\sigma `$. Then $`\kappa `$ will be referred to as an extended Scharlemann cycle, only when $`n_j4`$. A generalized $`S`$-cycle is the triple $`\{e_1,e_2,e_3\}`$ of mutually parallel positive edges in succession and $`e_2`$ is a level edge, only when $`n_j3`$.

###### Lemma 2.3.

Assume that $`M(\gamma _j)`$ is either of type $`𝒮`$, $`𝒜`$ or $`𝒯`$. If $`G_i`$ has a Scharlemann cycle then $`\widehat{F}_j`$ must be separating, and so $`n_j`$ is even. Furthermore, for cases $`𝒜`$ and $`𝒯`$, the edges of a Scharlemann cycle do no lie in a disk in $`\widehat{F}_j`$.

###### Proof.

Let $`E`$ be a disk face bounded by a Scharlemann cycle with a label pair, say $`\{1,2\}`$, in $`G_i`$. Let $`V_{12}`$ be the $`1`$-handle cut from $`V_{\gamma _j}`$ by the vertices $`1`$ and $`2`$ of $`G_j`$. (When $`n_j=2`$, $`V_{12}`$ is chosen to meet $`E`$.) Then tubing $`\widehat{F}_j`$ along $`V_{12}`$ and compressing along $`E`$ gives a new surface $`R`$ in $`M(\gamma _j)`$, homeomorphic to $`\widehat{F}_j`$, that intersects $`V_{\gamma _j}`$ fewer times than $`\widehat{F}_j`$. If the original $`\widehat{F}_j`$ is non-separating, then so is $`R`$. Thus $`R`$ is essential for each case, a contradiction.

If the edges of the Scharlemann cycle lie in a disk $`D`$ in an annulus or torus $`\widehat{F}_j`$, then $`\text{nhd}(DV_{12}E)`$ is a once punctured lens space. By the irreducibility of $`M(\gamma _j)`$, $`M(\gamma _j)`$ is a lens space, so neither of type $`𝒜`$ nor of type $`𝒯`$. ∎

###### Lemma 2.4.

* If $`G_j`$ is of type $`𝒮,𝒜`$ or $`𝒯`$, then $`G_i`$ cannot have a level edge. If $`G_j`$ is of type $`𝒫`$ or $``$, then $`G_i`$ has at most one label of level edges. If $`G_j`$ is of type $`𝒦`$, then $`G_i`$ has at most two labels of level edges.
* If $`G_j`$ is of type $`𝒫,`$ or $`𝒦`$, then $`G_i`$ cannot have a Scharlemann cycle. If $`G_j`$ is of type $`𝒮`$ or $`𝒜`$, then any two Scharlemann cycles of $`G_i`$ have the same label pair.
* When $`G_j`$ is of type $`𝒮`$, $`M(\gamma _j)`$ contains a projective plane if $`G_i`$ contains an $`S`$-cycle.
* If $`G_j`$ is of type $`𝒮`$, $`𝒜`$ or $`𝒯`$, then $`G_i`$ cannot have an extended $`S`$-cycle.
* If $`G_j`$ is of type $`𝒫`$, $``$ or $`𝒦`$, then $`G_i`$ cannot have a generalized $`S`$-cycle.

###### Proof.

(1) Let $`e`$ be a negative loop based at a vertex $`x`$ in $`G_j`$. Then $`\text{nhd}(xe)`$ is a Möbius band in $`\widehat{F}_j`$. Since only projective plane, Möbius band and Klein bottle can contain at most one, one and two Möbius bands respectively, the conclusions follow.

(2) When $`G_j`$ is of type $`𝒫`$, $``$ or $`𝒦`$, assume for contradiction that $`G_i`$ contains a Scharlemann cycle. Then the construction in the proof of Lemma 2.3 gives a new surface homeomorphic to $`\widehat{F}_j`$ in $`M(\gamma _j)`$, which meets $`V_{\gamma _j}`$ fewer times than $`\widehat{F}_j`$. This contradicts the minimality of $`n_j`$.

When $`G_j`$ is of type $`𝒮`$ or $`𝒜`$, this is \[GL1, Theorem 2.4\] or \[W3, Lemma 5.4(2)\], respectively.

(3) Let $`\{e_1,e_2\}`$ be an $`S`$-cycle in $`G_i`$ with label pair $`\{k,k+1\}`$. Let $`v_h`$ be the $`h`$-th vertex of $`G_j`$ for $`h=k,k+1`$, and let $`H`$ be the part of $`V_{\gamma _j}`$ between $`v_k`$ and $`v_{k+1}`$. Let $`D`$ be the disk face bounded by the $`S`$-cycle, and let $`A`$ be the Möbius band obtained by taking $`HD`$ and shrinking $`H`$ radially to its core. Since $`A`$ is isotopic to the curve obtained from $`e_1e_2v_kv_{k+1}`$ by shrinking the vertices to points, $`A`$ bounds a disk on $`\widehat{F}_j`$. Thus $`M(\gamma _j)`$ contains a projective plane.

(4) These are \[W1, Lemma 2.3\], \[W3, Lemma 5.4(3)\] and \[BZ1, Lemma 2.10\], respectively.

(5) Let $`\{e_1,e_2,e_3\}`$ be a generalized $`S`$-cycle in $`G_i`$, where $`e_2`$ is a level edge with label $`k`$, and $`e_1,e_3`$ have the same label pair $`\{k1,k+1\}`$. Let $`v_h`$ be the $`h`$-th vertex of $`G_j`$ for $`h=k1,k,k+1`$, and let $`H`$ be the part of $`V_{\gamma _j}`$ between the vertices $`v_{k1}`$ and $`v_{k+1}`$ containing $`v_k`$. Then $`C=\text{nhd}(v_ke_2)`$ is a Möbius band in $`\widehat{F}_j`$. Let $`D`$ be the disk in $`F_i`$ representing the parallelism of $`e_1`$ and $`e_3`$ and containing $`e_2`$. Then we have a Möbius band $`A`$ from $`HD`$ as before. Note that $`\mathrm{Int}A`$ is disjoint from $`\widehat{F}_jC`$. Since $`A`$ is isotopic to the curve obtained from $`e_1e_3v_{k1}v_{k+1}`$ by shrinking $`v_{k\pm 1}`$ to points, $`A`$ is orientation-preserving on $`\widehat{F}_j`$.

If $`G_j`$ is of type $`𝒫`$, then $`A`$ above bounds a disk $`E`$ in $`\widehat{F}_jC`$. Thus $`AE`$ gives a new projective plane which meets $`V_{\gamma _j}`$ fewer times than $`n_j`$, a contradiction.

If $`G_j`$ is of type $``$, then either $`A`$ bounds a disk in $`\widehat{F}_jC`$ or $`A`$ is parallel to $`\widehat{F}_j`$. In the former, $`M(\gamma _j)`$ contains a projective plane, and hence $`M(\gamma _j)`$ is reducible, contradicting the irreducibility of $`M(\gamma _j)`$. In the latter, let $`A_1`$ be the annulus between $`A`$ and $`\widehat{F}_j`$. Then $`AA_1`$ is a Möbius band in $`M(\gamma _j)`$ which meets $`V_{\gamma _j}`$ fewer times than $`n_j`$.

If $`G_j`$ is of type $`𝒦`$, then $`A`$ bounds either a disk or a Möbius band $`B`$ in $`\widehat{F}_jC`$. In the former, $`M(\gamma _j)`$ contains a projective plane. By the irreducibility of $`M(\gamma _j)`$, $`M(\gamma _j)`$ is the lens space $`L(2,1)`$. But it is well known that $`L(2,1)`$ does not contain a Klein bottle \[BW\]. In the latter, $`AB`$ gives a new Klein bottle in $`M(\gamma _j)`$ which meets $`V_{\gamma _j}`$ fewer times than $`n_j`$ again. ∎

For simplicity we will call $`x`$ an $`sl`$-label of $`G_i`$ (or $`sl`$-vertex of $`G_j`$) if $`x`$ is a label of either a Scharlemann cycle or a level edge in $`G_i`$, according as $`\widehat{F}_j`$ is orientable or not. Thus Lemma 2.4 implies that $`G_i`$ contains at most 2, 1, 2, 1 or 2 $`sl`$-labels when $`G_j`$ is of type $`𝒮`$, $`𝒫`$, $`𝒜`$, $``$ or $`𝒦`$, respectively. When $`G_j`$ is of type $`𝒯`$, we do not need an upper bound for the number of $`sl`$-labels of $`G_i`$, but will show that at most three labels can be labels of $`S`$-cycles of $`G_i`$ unless $`M(\gamma _j)`$ contains a Klein bottle. (See Claim 8.1.)

###### Lemma 2.5.

Let $`F`$ be a family of mutually parallel positive edges in $`G_i`$, and let $`|F|`$ denote the number of edges in $`F`$.

* If $`G_j`$ is of type $`𝒮`$ or $`𝒜`$, $`|F|\frac{n_j}{2}+1`$. Furthermore if $`|F|=\frac{n_j}{2}+1`$, then the first two or the last two edges of $`F`$ form an $`S`$-cycle.
* If $`G_j`$ is of type $`𝒫`$ or $``$, $`|F|\frac{n_j+1}{2}`$. Furthermore if $`|F|=\frac{n_j+1}{2}`$, then the first or the last edge of $`F`$ is a level edge.
* If $`G_j`$ is of type $`𝒯`$ and $`n_j3`$, $`|F|\frac{n_j}{2}+2`$.
* If $`G_j`$ is of type $`𝒦`$ and $`n_j2`$, $`|F|\frac{n_j}{2}+1`$.

###### Proof.

(1) is \[W2, Lemma 1.5(1)\] and \[GW, Lemma 2.5(2)\]. (We remark that when $`G_j`$ is of type $`𝒜`$ and $`n_j=1`$, $`|F|1`$, because a pair of edges cannot be parallel in both graphs \[G1, Lemma 2.1\].) (3) is \[W2, Lemma 1.4\]. For (2), if $`|F|>\frac{n_j+1}{2}`$ then $`F`$ would contain either an $`S`$-cycle, a generalized $`S`$-cycle or two level edges with distinct labels, except the case where $`G_j`$ is of type $``$ and $`n_j=1`$. In the exceptional case, a pair of edges is parallel in both $`G_i`$ and $`G_j`$, a contradiction. (4) is similar to (2). ∎

###### Lemma 2.6.

Let $`F`$ be a family of mutually parallel negative edges in $`G_i`$.

* When $`G_j`$ is of type $`𝒮`$ or $`𝒫`$, $`|F|n_j1`$.
* When $`G_j`$ is of type $`𝒜`$, $``$ or $`𝒦`$, $`|F|n_j`$.

###### Proof.

(1) See \[G1, Lemma 2.3\]. (This is essentially proved in \[GLi, Section 5\].) (2) The argument of the proof of \[GW, Lemma 2.5(3)\] works well. (Also, see the proof of \[G1, Lemma 4.2\].) ∎

## 3. $`x`$-faces and non-orientable surfaces

In this section we assume that $`G_j`$ is of type $`𝒫`$ or $``$ (so we may assume that $`1`$ is the only possible $`sl`$-vertex of $`G_j`$ by Lemma 2.4), and thus all level edges of $`G_i`$ are level $`1`$-edges.

A disk face of the subgraph of $`G_i`$ consisting of all the vertices and positive $`x`$-edges of $`G_i`$ is called an $`x`$-face. Remark that the boundary of an $`x`$-face $`D`$ may be not a circle, that is, $`D`$ may contain a double edge, and more than two edges of $`D`$ may be incident to a vertex on $`D`$ (see Figure 2.1 in \[HM\]). A cycle in $`G_i`$ is a two-cornered cycle if it is the boundary of a disk face containing only $`01`$-corners, $`12`$-corners and positive edges, only when $`n_j3`$. Recall that $`0`$ denotes $`n_j`$. A two-cornered cycle must contain both kinds of corners, because $`G_i`$ cannot contain a Scharlemann cycle by Lemma 2.4. Also, it contains at least one $`02`$-edge. For convenience, when the labels appear in anticlockwise order around the boundary of a vertex $`v`$ of $`G_i`$, given three distinct labels $`x_1,x_2,x_3`$, we say $`x_1<x_2<x_3`$ if $`x_1,x_2,x_3`$ appear in anticlockwise order on some interval in $`v`$ containing $`n_j`$ edge endpoints. Thus three expressions $`x_1<x_2<x_3`$, $`x_2<x_3<x_1`$ and $`x_3<x_1<x_2`$ are equivalent.

###### Proposition 3.1.

Suppose that $`n_j3`$. An $`x`$-face, $`x1`$, in $`G_i`$ contains a pair of two-cornered cycles sharing a level $`1`$-edge.

###### Proof.

Let $`\mathrm{\Gamma }_D`$ be the subgraph of $`G_i`$ in an $`x`$-face $`D`$. There is a possibility that $`D`$ is not a circle as mentioned before. Since we will find a pair of two-cornered cycles within $`D`$, we can cut formally the graph $`G_iD`$ along double edges of $`D`$ and at vertices to which more than two edges of $`D`$ are incident to so that $`D`$ is deformed into a circle. (See also Figure 5.1 in \[HM\].) Thus we may assume that $`D`$ is a circle. We may assume that the labels appear in anticlockwise order around the boundary of each vertex.

Suppose that $`D`$ has a diagonal edge $`d`$ with distinct labels $`\{a,b\}`$, which must differ from $`x`$ because $`D`$ is an $`x`$-face, as in Figure 2(a). Assume without loss of generality that $`a<x<b`$. Formally construct a new $`x`$-face $`D^{}`$ as follows. Keep all corners and edges of $`\mathrm{\Gamma }_D`$ to the right of $`d`$ (when $`d`$ is directed from $`a`$ to $`b`$), discard all corners and edges to the left of $`d`$, and then insert additional edges to the left of $`d`$, and parallel to $`d`$, until you first reach label $`x`$ at one or both ends of this parallel family of edges, as in Figure 2(b). In particular, these additional edges contain no edges of two-cornered cycles or Scharlemann cycles of the graph on the new $`x`$-face $`D^{}`$.

Repeat the above process for every diagonal edge which is not a level $`1`$-edge, then get a new $`x`$-face $`E`$ and a graph $`\mathrm{\Gamma }_E`$ in $`E`$. All diagonal edges of $`\mathrm{\Gamma }_E`$ are level $`1`$-edges, and all (and only) boundary edges are $`x`$-edges, where the label $`x`$ possibly appear on both ends, say level $`x`$-edges.

###### Claim 3.2.

$`\mathrm{\Gamma }_E`$ contains a level $`1`$-edge.

###### Proof of Claim 3.2.

Assume that $`\mathrm{\Gamma }_E`$ contains no level $`1`$-edges, and so no diagonal edges. We first show that if for some vertex $`v`$ of $`\mathrm{\Gamma }_E`$ two boundary edges are incident to $`v`$ with label $`x`$, then these should be level $`x`$-edges. For, $`n_j+1`$ edges are incident to $`v`$ in $`\mathrm{\Gamma }_E`$. If $`n_j`$ is even, more than $`\frac{n_j}{2}`$ mutually parallel edges are incident to $`v`$, and so one of these edges should be a level edge different from a level $`x`$-edge (recall that $`\mathrm{\Gamma }_E`$ cannot contain a Scharlemann cycle), a contradiction. If $`n_j`$ is odd, two families of $`\frac{n_j+1}{2}`$ mutually parallel edges are incident to $`v`$ by Lemma 2.5(2), and the boundary edge of each family should be a level $`x`$-edge by the same reason above.

Consider the cycle $`\sigma `$ consisting of boundary $`x`$-edges of $`\mathrm{\Gamma }_E`$. Assume that $`\sigma `$ has an $`x`$-edge which is not a level $`x`$-edge. So the only one end has label $`x`$ at $`v_1`$, say. By the fact we just proved, another $`x`$-edge incident to $`v_1`$ does not have label $`x`$ at $`v_1`$. Thus this edge has label $`x`$ at the other end $`v_2`$, say. After repeating this process, we are led to show that $`\sigma `$ is a great $`x`$-cycle in the terminology of \[CGLS\]. By the same argument in the proof of Lemma 2.6.2 of \[CGLS\], $`\mathrm{\Gamma }_E`$ contains a Scharlemann cycle, since $`\mathrm{\Gamma }_E`$ does not contain level edges in its interior, a contradiction.

If all edges of $`\sigma `$ are level $`x`$-edges, then we have a great $`x+1`$-cycle just inside $`\sigma `$. Thus we still find a Scharlemann cycle, a contradiction. (See also \[HM, Lemma 5.2\].) ∎

Let $`e`$ be a level $`1`$-edge. So it does not belong to $`\mathrm{\Gamma }_E`$. Let $`E_1`$ and $`E_2`$ be the faces of $`\mathrm{\Gamma }_E`$ adjacent to $`e`$. Assume for contradiction that $`E_1`$ (or $`E_2`$) is not a two-cornered cycle. Note that $`E_1`$ may contain many level $`1`$-edges. Let $`\{a_k,a_k+1\}`$, $`k=1,\mathrm{},n`$, be the consecutive label pairs of the corners between successive level $`1`$-edges on $`E_1`$, which appear in order around $`E_1`$, when one runs clockwise around $`E_1`$ starting at one end of $`e`$, as in Figure 3(a). Then some $`a_k`$ is neither $`0`$ nor $`1`$. Since $`a_1=1`$ and $`a_n=0`$, there are indices $`l`$ and $`m`$ so that $`a_k=0`$ or $`1`$ when $`1k<l`$ or $`k=m`$, and $`a_k0,1`$ when $`lk<m`$. Consider the edges of the parallelism class containing each $`\{a_{k1}+1,a_k\}`$-edge, $`lkm`$. Note that among these edges a level $`x`$-edge on the boundary of $`\mathrm{\Gamma }_E`$ is the only possible level edge, and there is no $`x`$-edge except on the boundary. See Figure 3(b). Then we have $`xa_k<a_{k1}+1x`$, and so $`xa_ka_{k1}<x`$. Finally we have $`xa_ma_{m1}\mathrm{}a_la_{l1}<x`$. This is impossible because $`a_{l1},a_m=0`$ or $`1`$. Thus we have shown that any face adjacent to a level $`1`$-edge is two-cornered. ∎

In fact, we can see from the argument above that $`a_1=\mathrm{}=a_i=1`$ and $`a_{i+1}=\mathrm{}=a_n=0`$ for some $`i`$. That is, when we go along a two-cornered cycle from a level $`1`$-edge in some direction, $`12`$-corners appear successively, $`23`$-corners appear after them, and we reach a level $`1`$-edge (possibly, a different one from the start).

Recall that $`1`$ is the only possible $`sl`$-label of $`G_i`$. The next theorem essentially follows from the argument of \[H, Section 7\].

###### Theorem 3.3.

If $`G_j`$ is of type $`𝒫`$, then $`G_i`$ cannot contain an $`x`$-face for a non-$`sl`$-label $`x`$ of $`G_i`$.

###### Proof.

Assume that $`G_i`$ contains such an $`x`$-face. If $`n_j=2`$, then a boundary of each face in the $`x`$-face is a Scharlemann cycle or contains both a level $`1`$-edge and a level $`2`$-edge, contradicting Lemma 2.4(1) and (2). Thus we may assume that $`n_j3`$. Applying Proposition 3.1, $`G_i`$ contains a pair of two-cornered cycles sharing a level $`1`$-edge $`e`$.

Let $`\widehat{S}`$ be the sphere which is the boundary of a regular neighborhood of $`\widehat{F}_j`$ in $`M(\gamma _j)`$, and let $`S=\widehat{S}M`$. The arc components of $`F_iS`$ give rise to a pair of labelled graphs ($`G_i^S,G_S`$) as usual, where $`G_S`$ is a double cover of $`G_j`$. Then $`G_i^S`$ contains an $`S`$-cycle $`\sigma `$ corresponding to the level $`1`$-edge $`e`$. We may assume that $`\sigma `$ has label pair $`\{1,2\}`$. Also, two cycles adjacent to $`\sigma `$ in $`G_i^S`$ contain only two types of corners, $`01`$-corners and $`23`$-corners. Let $`E_1`$ and $`E_2`$ be the faces of $`G_i^S`$ bounded by these cycles respectively. The edges of $`\sigma `$ separate $`\widehat{S}`$ into two disks, and two vertices $`0`$ and $`3`$ of $`G_S`$ are contained in the same disk component, say $`D_0`$, because of the existence of $`03`$-edges. Let $`D_1`$ be an expansion of $`D_0`$ containing the fat vertices $`1`$ and $`2`$ in $`\widehat{S}`$, and regard it as properly embedded in $`X=\text{nhd}(D_1V_{01}V_{23}E_1E_2)`$ where $`V_{01}`$ and $`V_{23}`$ are defined as in the proof of Lemma 2.3. Since $`E_1`$ and $`E_2`$ are non-separating on the boundary of the genus two handlebody $`\text{nhd}(D_1V_{01}V_{23})`$, $`X`$ is either a $`2`$-sphere or the disjoint union of a $`2`$-sphere and a torus. The latter happens only when $`E_1`$ and $`E_2`$ are parallel on the boundary of $`\text{nhd}(D_1V_{01}V_{23})`$. In this case, $`D_1`$ lies in the parallelism annulus. Thus $`D_1`$ cuts the $`2`$-sphere component of $`X`$ into two disk parts, one of which is parallel to $`D_1`$, in any case. Let $`D`$ be the other disk part and then extend $`D`$ down to $`\widehat{F}_j`$ along an annulus $`A=D\times I`$, using the $`I`$-bundle structure of $`\text{nhd}(\widehat{F}_j)`$. Note that the boundary component of $`A`$ which lies on $`\widehat{F}_j`$ bounds a Möbius band $`B`$ intersecting the core of $`V_{\gamma _j}`$ in a single point. In particular, $`DAB`$ is a projective plane in $`M(\gamma _j)`$. Since $`|DV_{\gamma _j}||D_0V_{\gamma _j}|2=n_j3`$, $`|AV_{\gamma _j}|=0`$ and $`|BV_{\gamma _j}|=1`$, this projective plane intersects the core of $`V_{\gamma _j}`$ in less than $`n_j`$ points. This contradicts the minimality of $`n_j`$. ∎

###### Theorem 3.4.

If $`G_j`$ is of type $``$ with $`n_j2`$, then $`G_i`$ cannot contain an $`x`$-face for a non-$`sl`$-label $`x`$ of $`G_i`$.

###### Proof.

The same argument in the proof of Theorem 3.3 applies here. Assume that $`G_i`$ contains an $`x`$-face for a non-$`sl`$-label $`x`$. Applying Proposition 3.1, $`G_i`$ contains a pair of two-cornered cycles sharing a level $`1`$-edge $`e`$. In particular, we can assume that one of the pair contains a single level $`1`$-edge. This is guaranteed by choosing the level $`1`$-edge $`e`$ to be outermost in the $`x`$-face. In the same notation as before, however, the edges of $`\sigma `$ separate $`\widehat{S}`$, which is an annulus, into two annuli, and so $`D_1`$ is an annulus. Also, we may assume that $`E_1`$ contains only one $`12`$-edge.

Let $`W=\text{nhd}(D_1V_{01}V_{23})`$ and let $`X=W\text{nhd}(E_1E_2)`$ as before. We may assume that $`D_1`$ is properly embedded in $`W`$ and $`X`$. Thus $`W`$ consists of a solid torus $`\text{nhd}(D_1)`$ and the two $`1`$-handles attached there. Now $`\pi _1(W)=x,y,t`$, where taking as base “point” a thick ball negihborhood of a meridian disk of $`\text{nhd}(D_1)`$, which contains the $`12`$-edge of $`E_1`$ and the four attaching disks of two $`1`$-handles $`V_{01}`$ and $`V_{23}`$, $`x`$ is represented by a core of $`V_{23}`$ going from vertex $`2`$ to vertex $`3`$, $`y`$ is represented by a core of $`V_{01}`$ going from vertex $`0`$ to vertex $`1`$, and $`t`$ is represented by the $`12`$-edge of $`\sigma `$ on $`E_2`$ oriented from vertex $`1`$ to vertex $`2`$. In $`\pi _1(W)`$, $`[E_2]`$ (with a clockwise orientation) contains the sequence $`ytx`$, but $`[E_1]`$ has no such sequence by the fact that $`E_1`$ has only one level $`12`$-edge. Hence $`E_1`$ and $`E_2`$ are not parallel on $`W`$. Clearly, both are non-separating on $`W`$. Thus the boundary of $`W\text{nhd}(E_1)`$ is a genus two surface, but $`X`$ is either a torus or the disjoint union of two tori, according to whether $`E_2`$ is non-separating on the genus two surface or not. In the former, one component of $`D_1`$ is essential on the torus. If not, $`\widehat{F}_j`$ is compressible, and hence $`M(\gamma _j)`$ contains a projective plane, which contradicts the irreducibility of $`M(\gamma _j)`$. Therefore the frontier of $`X`$ is an annulus. In the latter, the frontier of $`X`$ is the disjoint union of an annulus and a torus. Thus in either case, we have an annulus component among the frontier of $`X`$. In particular, $`D_1`$ divides it into two annuli, one of which is parallel to $`D_1`$. The rest of the proof is exactly the same as previous, and we would have a new Möbius band having fewer intersection with $`V_{\gamma _j}`$. ∎

## 4. $`x`$-faces and orientable surfaces

In this section we assume that $`G_j`$ is of type $`𝒮`$ or $`𝒜`$. By Lemma 2.4(2) we may assume that $`G_i`$ contains only $`12`$-Scharlemann cycles, if they exist.

An $`x`$-face in $`G_i`$ is defined as previous. A cycle in $`G_i`$ is a two-cornered cycle, slightly different from previous, if it is the boundary of a disk face containing only $`01`$-corners, $`23`$-corners and positive edges, and additionally it contains at least one edge of a $`12`$-Scharlemann cycle. A two-cornered cycle must contain both types of corners and a $`03`$-edge. A cluster $`C`$ is a connected subgraph of $`G_i`$ satisfying that

* $`C`$ consists of $`12`$-Scharlemann cycles and two-cornered cycles,
* every $`12`$-edge of $`C`$ belongs to both a Scharlemann cycle and a two-cornered cycle, and
* $`C`$ contains no cut vertex.

See Figure 4.

###### Proposition 4.1.

Suppose that $`n_j3`$. An $`x`$-face, $`x1,2`$, in $`G_i`$ contains a cluster $`C`$.

###### Proof.

Let $`\mathrm{\Gamma }_D`$ be the subgraph of $`G_i`$ in an $`x`$-face $`D`$. As in the previous, we may assume that $`D`$ is a circle. Also assume that the labels appear anticlockwisely.

For all diagonal edges of $`D`$ which are not of $`12`$-Scharlemann cycles (also these are neither $`x`$-edges nor level edges), apply the same argument in the proof of Proposition 3.1. Then we get a new $`x`$-face $`E`$ and a graph $`\mathrm{\Gamma }_E`$ in $`E`$ so that all diagonal edges are of $`12`$-Scharlemann cycles and all (and only) boundary edges are $`x`$-edges. Furthermore the additional edges contain no edges of Scharlemann cycles or two-cornered cycles of $`\mathrm{\Gamma }_E`$. Remark that a level $`x`$-edge can appear on the boundary of the graph.

###### Claim 4.2.

$`\mathrm{\Gamma }_E`$ contains a $`12`$-Scharlemann cycle, so does $`\mathrm{\Gamma }_D`$.

###### Proof of Claim 4.2.

It is clear from the proof of Claim 3.2. ∎

This means that $`\widehat{F}_j`$ must be separating and $`n_j`$ is even by Lemma 2.3. The parity rule guarantees that each edge of $`\mathrm{\Gamma }_E`$ connects vertices with one label even and the other label odd, and so there are no level $`x`$-edges.

Any $`12`$-edge of a Scharlemann cycle does not belong to $`\mathrm{\Gamma }_E`$. Consider the face $`E_1`$ of $`\mathrm{\Gamma }_E`$ which is adjacent to the $`12`$-edge and whose boundary is not the Scharlemann cycle. It is possible that $`E_1`$ contains more than one $`12`$-edges of Scharlemann cycles. Again, let $`\{a_k,a_k+1\}`$, $`k=1,\mathrm{},n`$, be the consecutive label pairs of the corners between two consecutive $`12`$-edges of Scharlemann cycles when one runs clockwise around $`E_1`$. Note that $`a_1=2`$ and $`a_n=0`$.

Assume for contradiction that $`E_1`$ is not a two-cornered cycle. Since some $`a_k`$ then is neither $`0`$ nor $`2`$, there are indices $`l`$ and $`m`$ so that $`a_k=0`$ or $`2`$ when $`1k<l`$ or $`k=m`$, and $`a_k0,2`$ when $`lk<m`$.

Consider the edges of the parallelism class containing each $`\{a_{k1}+1,a_k\}`$-edge for $`lkm`$. Since there are neither Scharlemann cycles nor level edges among these edges, one finds that $`xa_k<a_{k1}+1x`$, and hence $`xa_ka_{k1}<x`$. And so $`xa_ma_{m1}\mathrm{}a_la_{l1}<x`$. This is impossible because $`a_{l1},a_m=0`$ or $`2`$ and all $`a_k`$’s are even by the parity rule. Hence $`E_1`$ is a two-cornered cycle.

Thus we have shown that any face next to a Scharlemann cycle in $`\mathrm{\Gamma }_E`$ is two-cornered. Let $`C`$ be the union of all the Scharlemann cycles and all the two-cornered cycles adjacent to each 12-edges of the Scharlemann cycles. If necessary, choose a block of $`C`$. Then it is a desired cluster in $`\mathrm{\Gamma }_E`$ and so in $`\mathrm{\Gamma }_D`$. ∎

Furthermore, we can see from the argument that $`a_1=\mathrm{}=a_i=2`$ and $`a_{i+1}=\mathrm{}=a_n=0`$ for some $`i`$.

Let $`R`$ be the twice-punctured sphere obtained from $`\widehat{F}_j`$ by deleting two fat vertices $`1`$ and $`2`$ (if $`G_j`$ is of type $`𝒜`$, then use $`\widehat{F}_j`$ after capping off two boundary circles by disks). The family of all $`12`$-edges of a Scharlemann cycle in the cluster $`C`$ separates $`R`$ into disks, and one of those disks contains both vertices $`0`$ and $`3`$ of $`G_j`$, because of the existence of $`03`$-edges in $`C`$. The two $`12`$-edges bounding such a disk are called good edges of $`C`$. Thus each Scharlemann cycle in $`C`$ has exactly two good edges.

Let $`\mathrm{\Lambda }`$ be the maximal dual graph of $`C`$ whose vertices are dual to Scharlemann cycles and two-cornered cycles containing good edges, and edges are dual to good edges of $`C`$ as depicted in Figure 4. Thus in $`\mathrm{\Lambda }`$, a vertex dual to a Scharlemann cycle has valency $`2`$, and a vertex dual to a two-cornered cycle has valency the number of good edges of the two-cornered cycle. Furthermore $`\mathrm{\Lambda }`$ is a forest according to the construction of $`C`$. That is, each component of $`\mathrm{\Lambda }`$ is a tree. Let $`\sigma `$ be a two-cornered cycle with a good edge in $`C`$. Then each $`12`$-edge, which is not a good one, in $`\sigma `$ contributes to the number of components of $`\mathrm{\Lambda }`$ by adding $`1`$. Consequently there is a component $`\mathrm{\Lambda }_g`$ of $`\mathrm{\Lambda }`$ so that all $`12`$-edges of its dual two-cornered cycles are good.

Hereafter, we consider the subgraph $`C_g`$ of $`C`$, dual to $`\mathrm{\Lambda }_g`$. Say, $`C_g`$ contains $`n`$ Scharlemann cycles, and so $`2n`$ good edges and $`n+1`$ two-cornered cycles. A two-cornered cycle dual to an end vertex of the tree $`\mathrm{\Lambda }_g`$ has only one good edge. Choose one $`e_1`$ of the nearest edges to vertex $`0`$ (or $`3`$) among them, that is, there are no such good edges between $`e_1`$ and vertex $`0`$ in $`R`$. Let $`\sigma _g`$ and $`\sigma _1`$ be the Scharlemann cycle and two-cornered cycle adjacent to $`e_1`$ respectively. Note that $`\sigma _1`$ has only one $`12`$-edge. Then $`\sigma _g`$ has another good edge $`e_2`$, and $`e_1`$ and $`e_2`$ bound a disk $`D_g`$ containing $`0`$ and $`3`$ in $`R`$. Note that the boundaries of the faces bounded by Scharlemann cycles are parallel on a torus obtained from $`R`$ by attaching an annulus $`V_{12}`$. Thus exactly $`n1`$ out of $`2n`$ good edges are not contained in $`D_g`$. Therefore we have another two-cornered cycle $`\sigma _2`$ all of whose $`12`$-edges lie in $`D_g`$. Consequently all edges (consisting of $`01`$-edges, $`12`$-edges, $`23`$-edges and $`03`$-edges) of $`\sigma _1`$ and $`\sigma _2`$ lie in $`D_g`$. Furthermore if $`\sigma _2`$ has only one good $`12`$-edge, then the two good edges of $`\sigma _1`$ and $`\sigma _2`$ lie on different sides of the vertices $`0`$ and $`3`$ in $`D_g`$ by the choice of $`\sigma _1`$. Such $`\sigma _1,\sigma _2`$ are called a seemly pair. Then we can say:

###### Proposition 4.3.

There is a seemly pair of two-cornered cycles in $`C`$.

From now we apply the argument in \[H, Section 6\] to get the following two theorems. Recall that $`1,2`$ are the only possible $`sl`$-labels of $`G_i`$

###### Theorem 4.4.

If $`G_j`$ is of type $`𝒮`$, then $`G_i`$ cannot contain an $`x`$-face for a non-$`sl`$-label $`x`$ of $`G_i`$.

###### Proof.

Suppose that $`G_i`$ contains such an $`x`$-face. Note that $`n_j3`$ by Lemma 2.2. We continue the preceding argument.

Let $`E`$ be the disk bounded by $`\sigma _g`$. Then $`L=\mathrm{nhd}((\widehat{F}_j\mathrm{Int}D_g)V_{12}E)`$ is a punctured lens space in $`M(\gamma _j)`$. Since $`L`$ is a reducing sphere in $`M(\gamma _j)`$, $`|LV_{\gamma _j}|=2|(\widehat{F}_j\mathrm{Int}D_g)V_{\gamma _j}|2n_j`$ by the minimality of $`n_j`$. Thus $`|\mathrm{Int}D_gV_{\gamma _j}|\frac{n_j}{2}1`$. Let $`X_D^{}=\text{nhd}(D_gV_{01}V_{23})`$ and $`X_F^{}=\text{nhd}(\widehat{F}_jV_{01}V_{23})`$. Then $`X_D^{}`$ is a genus two handlebody and $`X_F^{}`$ is a once-punctured genus two handlebody. The genus two torus component of $`X_F^{}`$ is referred to as the outer boundary of $`X_F^{}`$. Let $`E_i`$ be the face bounded by the two-cornered cycle $`\sigma _i`$ for $`i=1,2`$. The point is that all edges of $`\sigma _i`$ are contained in $`D_g`$. Let $`X_D=X_D^{}\text{nhd}(E_1E_2)`$ and $`X_F=X_F^{}\text{nhd}(E_1E_2)`$ as in Figure 5. Since $`E_1`$ and $`E_2`$ are non-separating on $`X_D^{}`$ and $`X_F^{}`$, both $`X_D`$ and the outer components of $`X_F`$ are either a $`2`$-sphere or the disjoint union of a $`2`$-sphere and a torus, simultaneously. Note that the latter case occurs only when $`E_1`$ and $`E_2`$ are parallel on the boundary of $`X_D^{}`$ or $`X_F^{}`$.

First, assume that $`X_D`$ is a $`2`$-sphere $`S_D`$, and the outer component of $`X_F`$ is a $`2`$-sphere $`S_F`$. If $`X_D`$ is not a $`3`$-ball, then $`S_D`$ is a reducing sphere. But $`|S_DV_{\gamma _j}|=2|\mathrm{Int}D_gV_{\gamma _j}|n_j2`$, contradicting the minimality of $`n_j`$. Thus it should be a $`3`$-ball, and so $`X_F`$ is homeomorphic to $`S^2\times I`$. Thus $`S_F`$ is isotopic to $`\widehat{F}_j`$, contradicting the minimality of $`n_j`$ again.

Next, assume that $`X_D`$ is the disjoint union of a $`2`$-sphere and a torus, $`S_DT_D`$ and the outer components of $`X_F`$ are also the disjoint union of a $`2`$-sphere and a torus, $`S_FT_F`$. Recall that this case occurs whenever $`E_1`$ and $`E_2`$ cobound an annulus in $`X_D^{}`$ and $`X_F^{}`$. This is possible only when $`\sigma _2`$ corresponds to an end vertex of $`\mathrm{\Lambda }_g`$ with the same number of $`01`$-corners and $`23`$-corners as those of $`\sigma _1`$. Let $`D^{}`$ be the intersection of $`X_D`$ and the inner sphere component of $`X_F`$. By the choice of the seemly pair, this annulus in $`X_D^{}`$ contains $`D^{}`$, so does $`S_D`$. Similarly $`S_F`$ contains a pushoff of $`RD_g`$.

If $`S_D`$ is non-separating in $`M(\gamma _j)`$, then it is a reducing sphere with $`|S_DV_{\gamma _j}|n_j2`$, contradicting. Thus $`S_D`$ is separating in $`M(\gamma _j)`$. Let $`X_D^{\prime \prime }`$ be the manifold bounded by $`S_D`$ containing $`T_D`$ in $`M(\gamma _j)`$. If $`X_D^{\prime \prime }`$ is not a $`3`$-ball, then $`S_D`$ is a reducing sphere with less intersection with $`V_{\gamma _j}`$. Thus it should be a $`3`$-ball, and so $`S_F`$ is isotopic to $`\widehat{F}_j`$, contradicting again. This completes the proof. ∎

###### Theorem 4.5.

If $`G_j`$ is of type $`𝒜`$ with $`n_j3`$, then $`G_i`$ cannot contain an $`x`$-face for a non-$`sl`$-label $`x`$ of $`G_i`$.

###### Proof.

Suppose that $`G_i`$ contains such an $`x`$-face. Again we continue the argument stated before Proposition 4.3. The proof is divided into three cases. Recall that $`R`$ is a twice-punctured sphere obtained from $`\widehat{F}_j`$ by deleting two vertices $`1`$ and $`2`$ and then capping off $`\widehat{F}_j`$ by two disks, and that $`D_g`$ lies on $`R`$.

First, suppose that $`D_g`$ contains $`\widehat{F}_j`$. Then the edges of the Scharlemann cycle $`\sigma _g`$ lie in a disk in $`\widehat{F}_j`$, contradicting Lemma 2.3.

Second, suppose that $`D_g`$ does not contain any component of $`\widehat{F}_j`$. Then $`D_g`$ is contained in $`\widehat{F}_j`$. The proof is similar to that of the preceding theorem. Recall that $`E_i`$ is the face bounded by the two-cornered cycle $`\sigma _i`$ for $`i=1,2`$. Let $`X_D=\text{nhd}(D_gV_{01}V_{23}E_1E_2)`$ and $`X_F=\text{nhd}(\widehat{F}_jV_{01}V_{23}E_1E_2)`$. Then $`X_D`$ is either a $`2`$-sphere or the disjoint union of a $`2`$-sphere and a torus. Also, the frontier of $`X_F`$ has a copy of $`\widehat{F}_j`$, and the remaining part is referred to as the outer components. It can be seen that the outer components consist of either a single annulus or the disjoint union of an annulus and a torus by the choice of the seemly pair. ($`X_D`$ is disconnected if and only if the outer components of the frontier of $`X_F`$ are disconnected.) In either case, we have an annular component $`A_F`$. Then $`A_F`$ is obtained from $`\widehat{F}_j`$ by replacing $`D_g`$ with a proper disk which is a part of the $`2`$-sphere component of $`X_D`$. Since $`M(\gamma _j)`$ is irreducible by the assumption in Section 1, the $`2`$-sphere component of $`X_D`$ bounds a $`3`$-ball. Hence $`A_F`$ is isotopic to $`\widehat{F}_j`$. This contradicts the minimality of $`n_j`$.

Finally suppose that $`D_g`$ contains exactly one component of $`\widehat{F}_j`$. If there is a disk in $`D_g`$ which contains all edges of $`\sigma _1`$ and $`\sigma _2`$ and which does not contain the component of $`\widehat{F}_j`$, then the case reduces to the previous one. Otherwise, let $`A_1`$ be the annulus $`D_g\widehat{F}_j`$. Consider $`Y=\mathrm{nhd}((\widehat{F}_j\mathrm{Int}A_1)V_{12}E)`$, where $`E`$ is the face bounded by $`\sigma _g`$. Then the frontier $`Q`$ of $`Y`$ in $`M(\gamma _j)`$ is an essential annulus by Claim on page 430 of \[W3\]. Thus $`|QV_{\gamma _j}|=2|(\widehat{F}_j\mathrm{Int}A_1)V_{\gamma _j}|2n_j`$ by the minimality of $`n_j`$. Hence $`|\text{Int}A_1V_{\gamma _j}|\frac{n_j}{2}1`$. Let $`X_A=\text{nhd}(A_1V_{01}V_{23}E_1E_2)`$ and $`X_F=\text{nhd}(\widehat{F}_jV_{01}V_{23}E_1E_2)`$ again. Then the frontier of $`X_A`$ contains an annulus component $`A_A`$ by the same argument as in the proof of Theorem 3.4. (By the choice of the seemly pair, $`E_1`$ and $`E_2`$ are not parallel on the boundary of $`\text{nhd}(A_1V_{01}V_{23})`$ and $`\text{nhd}(\widehat{F}_jV_{01}V_{23})`$.) Also the outer components of the frontier of $`X_F`$ contain an annulus $`A_F`$. If $`A_A`$ is essential in $`M(\gamma _j)`$, then $`|A_AV_{\gamma _j}|2|\text{Int}A_1V_{\gamma _j}|n_j2`$, contradicting the minimality of $`n_j`$. Remark that $`A_A`$ is incompressible, because the central curve of $`A_A`$ is isotopic to the central curve of $`\widehat{F}_j`$. Thus $`A_A`$ should be boundary parallel. That is, there is a solid torus $`U`$ such that $`A_A`$ is a longitudinal annulus on $`U`$ and $`UA_AM(\gamma _j)`$. Then either $`\widehat{F}_j`$ is boundary parallel or one can isotope $`\widehat{F}_j`$ through $`U`$ to $`A_F`$, which intersects $`V_{\gamma _j}`$ fewer times than $`\widehat{F}_j`$. ∎

Remark that an extended Scharlemann cycle is one of the simplest form of $`x`$-faces. Thus two theorems above guarantee that if $`G_j`$ is of type $`𝒮`$ or $`𝒜`$, then $`G_i`$ cannot contain an extended Scharlemann cycle. We may emphasize that only an extended $`S`$-cycle was used in the literatures such as \[GW, W1\] etc.

## 5. Extremal block

The reduced graph $`\overline{G}_i`$ of $`G_i`$ is defined to be the graph obtained from $`G_i`$ by amalgamating each family of parallel edges into a single edge. Let $`G_i^+`$ denote the subgraph of $`G_i`$ consisting of all vertices and positive edges of $`G_i`$. When $`G_i`$ is of type $`𝒮`$, it is obvious that each component of $`G_i^+`$ has a disk support, that is, there is a disk in $`\widehat{F}_i`$ which contains the component in its interior. Even if $`G_i`$ is of type $`𝒫`$, the same is true, because any orientation-preserving loop in a projective plane is contractible.

###### Proposition 5.1.

If $`G_1`$ is of type $`𝒮`$ or $`𝒫`$ and $`G_2`$ is any of the six types, then each non-$`sl`$-vertex of $`G_1`$ has at least $`(\mathrm{\Delta }(\gamma _1,\gamma _2)1)n_2+\chi (\widehat{F}_2)`$ positive edge endpoints.

###### Proof.

Assume that there is a non-$`sl`$-vertex $`x`$ of $`G_1`$ which has more than $`n_2\chi (\widehat{F}_2)`$ negative edges. Then $`G_2`$ contains more than $`n_2\chi (\widehat{F}_2)`$ positive $`x`$-edges by the parity rule. Thus the subgraph $`\mathrm{\Gamma }_x`$ of $`G_2`$ consisting of all vertices and positive $`x`$-edges of $`G_2`$ has $`n_2`$ vertices and more than $`n_2\chi (\widehat{F}_2)`$ edges. Then an Euler characteristic calculation shows that $`\mathrm{\Gamma }_x`$ contains a disk face, which is an $`x`$-face. This contradicts Theorem 3.3 or 4.4. ∎

Suppose that $`G_1`$ is of type $`𝒮`$ or $`𝒫`$, and that $`\mathrm{\Delta }(\gamma _1,\gamma _2)2`$. By Lemmas 2.2 and 2.4, $`G_1`$ has a non-$`sl`$-vertex. Note that each of these vertices has therefore valency at least two in $`\overline{G}_1`$ by Lemmas 2.5 and 2.6. Now take an innermost component $`\mathrm{\Lambda }_0`$ of $`G_1^+`$ with a disk support $`D_0`$, which means that $`D_0G_1^+=\mathrm{\Lambda }_0`$. The subgraph $`\mathrm{\Lambda }_0`$ has therefore at most one $`sl`$-vertex.

Suppose that $`\mathrm{\Lambda }_0`$ is a single vertex. Then only negative edges are incident there. By Proposition 5.1, it is an $`sl`$-vertex. If $`G_1`$ is of type $`𝒮`$, the edges of a Scharlemann cycle of $`G_2`$ are incident there. Then one of the disks bounded by these edges contains non-$`sl`$-vertices, since $`n_13`$ by Lemma 2.2. Hence we can choose another innermost component of $`G_1^+`$ with more than one vertex and at most one $`sl`$-vertex. If $`G_1`$ is of type $`𝒫`$, a negative loop is incident there. Thus we can also choose another innermost component of $`G_1^+`$ which contains only non-$`sl`$-vertices.

We may therefore assume that $`\mathrm{\Lambda }_0`$ has more than one vertex. Then $`\mathrm{\Lambda }_0`$ has no cut vertex or at least two blocks with at most one cut vertex. Thus we can choose an innermost component $`\mathrm{\Lambda }`$ with a disk support $`D`$ after splitting $`\mathrm{\Lambda }_0`$ at all cut vertices, such that $`\mathrm{\Lambda }`$ has more than one vertex with at most one cut vertex. In such a case that $`\mathrm{\Lambda }`$ contains a cut vertex and a distinct $`sl`$-vertex, we can choose another innermost one containing no $`sl`$-vertex.

Such a subgraph $`\mathrm{\Lambda }`$ of $`G_1^+`$ is called an extremal block with a disk support $`D`$. A vertex of $`\mathrm{\Lambda }`$ is called a ghost vertex if it is either a cut vertex or an $`sl`$-vertex. We emphasize that $`\mathrm{\Lambda }`$ has more than one vertex and at most one ghost vertex $`y_0`$. A vertex of $`\mathrm{\Lambda }`$ is called a boundary vertex if there is an arc connecting it to $`D`$ whose interior is disjoint from $`\mathrm{\Lambda }`$, and an interior vertex otherwise. Then the preceding argument with Proposition 5.1 proves the following theorem which plays key role in this paper:

###### Theorem 5.2.

Suppose that $`G_1`$ is of type $`𝒮`$ or $`𝒫`$.

* If $`G_2`$ is of type $`𝒮`$, $`𝒫`$, $`𝒜`$ or $``$ with the assumption that $`\mathrm{\Delta }(\gamma _1,\gamma _2)2`$, then $`G_1`$ contains an extremal block $`\mathrm{\Lambda }`$ with a disk support $`D`$ so that each boundary vertex, except $`y_0`$, has at least $`n_2+\chi (\widehat{F}_2)`$ consecutive edge endpoints of $`\mathrm{\Lambda }`$.
* If $`G_2`$ is of type $`𝒯`$ or $`𝒦`$ with the assumption that $`\mathrm{\Delta }(\gamma _1,\gamma _2)3`$ and $`n_23`$ when $`G_2`$ is of type $`𝒯`$, and $`n_22`$ when $`G_2`$ is of type $`𝒦`$, then $`G_1`$ contains an extremal block $`\mathrm{\Lambda }`$ with a disk support $`D`$ so that each boundary vertex, except $`y_0`$, has at least $`2n_2`$ consecutive edge endpoints of $`\mathrm{\Lambda }`$.

## 6. $`(𝒮,𝒮)`$ case

###### Proof of Theorem 1.1.

Assume for contradiction that $`\mathrm{\Delta }(\gamma _1,\gamma _2)2`$. Theorem 5.2(1) says that $`G_1^+`$ contains such an extremal block $`\mathrm{\Lambda }`$ with a disk support that each boundary vertex, except $`y_0`$, has more than $`n_2`$ consecutive edge endpoints, so different all $`n_2`$ labels. We can choose a non-$`sl`$-label $`x`$ (at $`y_0`$ if it exists), unless $`G_2`$ is of type $`𝒮`$ and there is $`y_0`$ with only two edge endpoints which have the $`sl`$-labels. Since $`\mathrm{\Lambda }`$ has at least the same number of $`x`$-edges as that of vertices, it contains an $`x`$-face, contradicting Theorem 3.3 or 4.4.

For the exceptional case, consider $`\mathrm{\Lambda }y_0`$. Since all labels still appear on each vertex of $`\mathrm{\Lambda }y_0`$, the same argument above leads to a contradiction. ∎

## 7. $`(𝒮,𝒜)`$ case

###### Proof of Theorem 1.2.

Assume that $`\mathrm{\Delta }=\mathrm{\Delta }(\gamma _1,\gamma _2)2`$. Recall that $`M(\gamma _2)`$ is irreducible and boundary irreducible.

First, assume that $`n_23`$ when $`G_2`$ is of type $`𝒜`$ (or $`n_22`$ when of type $``$). Theorem 5.2(1) says that $`G_1^+`$ contains an extremal block $`\mathrm{\Lambda }`$ with a disk support such that each boundary vertex, except $`y_0`$, has all different $`n_2`$ labels. When $`G_2`$ is of type $``$, choose a non-$`sl`$-label $`x`$ at $`y_0`$, if it exists. Otherwise, $`x`$ is any non-$`sl`$-label. Then $`\mathrm{\Lambda }`$ has at least the same number of $`x`$-edges as that of vertices, and therefore $`\mathrm{\Lambda }`$ has an $`x`$-face, contradicting Theorem 3.4. So $`G_2`$ is of type $`𝒜`$.

###### Claim 7.1.

$`G_1`$ contains a Scharlemann cycle.

###### Proof of Claim 7.1.

Assume not. Choose any label $`x`$ (at $`y_0`$ if it exists). Then there is an $`x`$-edge at any vertex of $`\mathrm{\Lambda }`$. Hence $`\mathrm{\Lambda }`$ contains a great $`x`$-cycle, and so a Scharlemann cycle \[CGLS, Lemma 2.6.2\]. ∎

Thus we may assume that $`G_1`$ contains only $`12`$-Scharlemann cycles. Equivalently, $`sl`$-labels of $`G_1`$ are $`1`$ and $`2`$. By Lemma 2.3, $`\widehat{F}_2`$ is separating and $`n_2`$ is even.

###### Claim 7.2.

* $`\mathrm{\Lambda }`$ has no interior vertices;
* $`\mathrm{\Lambda }`$ has a ghost vertex $`y_0`$ such that only two edges are incident to $`y_0`$ in $`\mathrm{\Lambda }`$ with $`sl`$-labels $`1`$ and $`2`$; and
* $`n_2=4`$, and the two edges incident to $`y_0`$ are indeed a $`14`$-edge and a $`23`$-edge.

###### Proof of Claim 7.2.

If $`\mathrm{\Lambda }`$ has an interior vertex or has no ghost vertex, then let $`x`$ be any non-$`sl`$-label. Then $`\mathrm{\Lambda }`$ has at least the same number of $`x`$-edges as that of vertices, so contains an $`x`$-face, contradicting Theorem 4.5. Even if there is a ghost vertex $`y_0`$, we can choose a non-$`sl`$-label $`x`$ at $`y_0`$, unless (2) holds. Finally, assume $`n_26`$. Then we can choose a non-$`sl`$-label $`x`$ such that $`y_0`$ is not incident to an $`x`$-edge. Thus $`\mathrm{\Lambda }y_0`$ contains an $`x`$-face as above again. Even if $`n_2=4`$, there is still such a label $`x`$, unless the second conclusion of (3) holds. ∎

In fact, $`\mathrm{\Lambda }y_0`$ contains a $`12`$-Scharlemann cycle $`\sigma `$, because there is a $`1`$-edge at any vertex of $`\mathrm{\Lambda }`$ by (3), and hence $`\mathrm{\Lambda }y_0`$ contains a great $`1`$-cycle. By Lemma 2.3, the edges of $`\sigma `$ cuts $`\widehat{F}_2`$ into two annuli $`A_1,A_2`$ and some disks.

###### Claim 7.3.

$`\mathrm{\Lambda }`$ contains a $`34`$-edge.

###### Proof of Claim 7.3.

Assume not. Then $`\mathrm{\Lambda }`$ contains only $`12`$, $`14`$ and $`23`$-edges by the parity rule. Let $`y_0,y_1,\mathrm{},y_k`$ be the vertices of $`\mathrm{\Lambda }`$, numbered consecutively along $`\mathrm{\Lambda }`$, where the $`14`$-edge $`e_0`$ at $`y_0`$ is incident to $`y_1`$. (Since $`y_i`$ $`(i0)`$ is incident to at least four edges in $`\mathrm{\Lambda }`$, we see $`k>1`$.) Let $`e_1`$ be the $`3`$-edge at $`y_1`$, just before $`e_0`$. (This means that the two endpoints of $`e_0`$ and $`e_1`$ are successive around $`y_1`$.) If $`e_1`$ goes to $`y_k`$, then $`e_1`$ is a $`34`$-edge. So assume $`e_1`$ goes to $`y_i`$ for $`1<i<k`$. Thus $`e_1`$ has the label $`2`$ at $`y_i`$. Split $`\mathrm{\Lambda }`$ along $`e_1`$, and let $`\mathrm{\Lambda }^{}`$ be the part containing $`y_1,y_2,\mathrm{},y_i`$. Then $`\mathrm{\Lambda }^{}`$ has a $`3`$-face, contradicting Theorem 4.5. ∎

Hence the vertices $`3`$ and $`4`$ lie in the same component, and we can see that they lie in $`A_1`$ or $`A_2`$ indeed. Otherwise, the vertex $`3`$ or $`4`$ is incident to more than $`n_1`$ negative edges. Thus, $`G_1`$ contains a $`3`$-face or $`4`$-face, a contradiction. We may assume that both are in $`A_2`$. Let $`A_1^{}=\mathrm{cl}(\widehat{F}_2A_2)`$, and $`Y=\mathrm{nhd}(A_1^{}V_{12}E)`$, where $`E`$ is the face bounded by $`\sigma `$. Then the frontier of $`Y`$ gives an essential annulus (see \[W3, Claim on page 430\]), which meets $`V_{\gamma _2}`$ in two disks. This contradicts the minimality of $`n_2`$.

If $`n_2=1`$ when $`G_2`$ is of type $`𝒜`$, $`G_2`$ has only positive edges, and these edges are all parallel. This contradicts Lemma 2.5(1-2).

Finally assume $`n_2=2`$ when $`G_2`$ is of type $`𝒜`$ (or $`n_2=1`$ when of type $``$). Assume for contradiction that $`\mathrm{\Delta }3`$. Consider the reduced graph $`\overline{G}_2`$. An Euler characteristic calculation shows that each vertex of $`\overline{G}_2`$ has valency at most 4. By Lemmas 2.5(1-2) and and 2.6(1) the valency must be 4, so the graph looks like that in Figure 6 ((a) for type $`𝒜`$ and (b) for type $``$).

###### Claim 7.4.

In Figure 6(a), the two vertices have opposite signs.

###### Proof of Claim 7.4.

Assume not. Then $`G_2`$ has only positive edges. For a non-$`sl`$-label $`x`$ of $`G_2`$, let $`\mathrm{\Gamma }`$ be the subgraph of $`G_2`$ consisting of all vertices and all $`x`$-edges of $`G_2`$. Then an Euler characteristic calculation shows that $`\mathrm{\Gamma }`$ has a disk face, which is an $`x`$-face. This contradicts Theorem 3.3 or 4.4. ∎

Thus $`a`$ and $`d`$ are the families of positive edges and $`b`$ and $`c`$ are the families of negative edges. When $`G_1`$ is of type $`𝒫`$, this is impossible by Lemmas 2.5 and 2.6. When $`G_1`$ is of type $`𝒮`$, $`G_2`$ contains an $`S`$-cycle by Lemma 2.5, so $`M(\gamma _1)`$ contains a projective plane by Lemma 2.4(3), a contradiction to the previous result. ∎

We now give an example realizing the case $`\mathrm{\Delta }=2`$ in Theorem 1.2. Theorem 2.6 of \[EW\] shows that there is a hyperbolic manifold $`M`$ such that $`M(\gamma _1)=(S^1\times D^2)\mathrm{}L(2,1)`$ and $`M(\gamma _2)`$ is the union of $`C(2,1)`$ and $`Q(2p,2p)`$, for any integer $`p2`$, along a torus, with $`\mathrm{\Delta }(\gamma _1,\gamma _2)=2`$. We denote by $`C(r,s)`$ the cable space of type $`(r,s)`$, and by $`Q(r,s)`$ the Seifert fibered manifold with orbifold a disk with two cone points of index $`r`$ and $`s`$. Note that $`C(2,1)`$ contains a Möbius band and essential annulus with the boundaries on the outside torus, hitting the attached solid torus once and twice, respectively.

## 8. $`(𝒮,𝒯)`$ case

###### Proof of Theorem 1.3.

Assume that $`\mathrm{\Delta }=\mathrm{\Delta }(\gamma _1,\gamma _2)3`$. Recall that $`M(\gamma _2)`$ is irreducible and boundary irreducible.

First, assume that $`n_23`$. Theorem 5.2(2) says that $`G_1^+`$ contains an extremal block $`\mathrm{\Lambda }`$ with a disk support $`D`$ so that each boundary vertex, except $`y_0`$, has at least $`2n_2`$ consecutive edge endpoints of $`\mathrm{\Lambda }`$. If $`G_2`$ is of type $`𝒦`$, then we can choose a non-$`sl`$-label $`x`$ of $`G_1`$ by Lemma 2.4. Assume that $`G_2`$ is of type $`𝒯`$.

###### Claim 8.1.

Either $`G_1`$ has a label $`x`$, which is not a label of $`S`$-cycles in $`G_1`$, or $`M(\gamma _2)`$ contains a Klein bottle which meets $`V_{\gamma _2}`$ at least two times.

###### Proof of Claim 8.1.

If $`n_2=3`$, then $`G_1`$ does not have a Scharlemann cycle by Lemma 2.3. Hence any label is a desired one. Assume $`n_24`$. If $`G_1`$ has four labels of $`S`$-cycles, then there are two $`S`$-cycles whose label pairs are disjoint. Then $`M(\gamma _2)`$ contains a Klein bottle $`R`$ by the argument of the proof of \[GL2, Lemma 3.10\]. If $`R`$ meets $`V_{\gamma _2}`$ in a single meridian disk, then take a double covering torus $`\stackrel{~}{R}`$ of $`R`$ in $`M(\gamma _2)`$. By the assumption $`n_24`$, $`\stackrel{~}{R}`$ is compressible. Then $`M(\gamma _2)`$ is a Seifert fibered manifold, called a prism manifold, which has finite fundamental group. This contradicts the fact that $`M(\gamma _2)`$ is toroidal. Hence $`R`$ meets $`V_{\gamma _2}`$ at least two times. ∎

In the second conclusion of Claim 8.1, if the Klein bottle meets $`V_{\gamma _2}`$ just two times, then we jump to the case of type $`𝒦`$ where $`n_2=2`$ below. Thus we have a label $`x`$ of $`G_1`$ which is not an $`sl`$-label when $`G_2`$ is of type $`𝒦`$, or which is not a label of $`S`$-cycles otherwise.

Let $`\mathrm{\Lambda }^x`$ be the subgraph of $`\mathrm{\Lambda }`$ consisting of all vertices and $`x`$-edges. Then each boundary vertex of $`\mathrm{\Lambda }^x`$, except $`y_0`$, has at least two edges attached with label $`x`$, which cannot be parallel by Lemma 2.5(3-4). Note that $`\mathrm{\Lambda }^x`$ may not be connected. Then, apply the argument in Section 5 to the present situation; choose an extremal block $`\mathrm{\Lambda }^{}`$ of $`\mathrm{\Lambda }^x`$ with a disk support $`D^{}`$ in $`D`$, which we can define in a similar way.

Let $`v,e`$ and $`f`$ be the numbers of vertices, edges, and disk faces of $`\mathrm{\Lambda }^{}`$, respectively. Also let $`v_i,v_{}`$ and $`v_g`$ be the numbers of interior vertices, boundary vertices and ghost vertices. Hence $`v=v_i+v_{}`$ and $`v_g=0`$ or $`1`$.

Suppose that $`\mathrm{\Lambda }^{}`$ has a bigon. By Lemma 2.5, it contains either a generalized $`S`$-cycle or an extended $`S`$-cycle. (Recall that $`x`$ itself is not a label of $`S`$-cycle.) But this is impossible by Lemma 2.4. Thus each face of $`\mathrm{\Lambda }^{}`$ is a disk with at least $`3`$ sides. Hence we have $`3f+v_{}2e`$. Since $`\mathrm{\Lambda }^{}`$ has only disk faces, combined with $`ve+f=\chi (D^{})=1`$, we get $`e3v_i+2v_{}3`$. On the other hand, we have $`2(v_{}v_g)+\mathrm{\Delta }v_ie`$, because each boundary vertex of $`\mathrm{\Lambda }^{}`$, except $`y_0`$, has at least two edges attached with label $`x`$, and $`x`$ is not a label of level edges. These two inequalities give us that $`32v_g`$, a contradiction.

Assume that $`n_2=1`$ when $`G_2`$ is of type $`𝒯`$. Then $`G_2`$ has only positive edges. Thus it contains an $`x`$-face for a non-$`sl`$-label $`x`$ of $`G_2`$, contradicting Theorems 3.3 and 4.4.

Assume that $`n_2=2`$ when $`G_2`$ is of type $`𝒦`$. This case is done by Theorem 5.2(2) and the argument of \[JLOT, Section6\], which can be carried over without change.

Finally assume that $`n_2=2`$ when $`G_2`$ is of type $`𝒯`$ (or $`n_2=1`$ when of type $`𝒦`$). Assume for contradiction that $`\mathrm{\Delta }4`$. An Euler characteristic calculation on $`\overline{G}_2`$ shows that each vertex has valency at most 6. Then the graph looks like a subgraph of the graph shown in Figure 7 ((a) for type $`𝒯`$ and (b) for type $`𝒦`$) \[G1, Lemma 5.2\]. Here, $`p_i0`$ denotes the number of edges in each parallelism class.

###### Claim 8.2.

When $`G_2`$ is of type $`𝒯`$, all non-loop edges of $`G_2`$ are negative.

###### Proof of Claim 8.2.

This follows from the same argument as the proof of Claim 7.4. ∎

Thus $`p_1\frac{n_1}{2}+1`$, and $`p_in_11`$ for $`i=2,3,4,5`$ by Lemmas 2.5 and 2.6. Since $`\mathrm{\Delta }n_1(n_1+2)+4(n_11)=5n_12`$, $`\mathrm{\Delta }=4`$ and all $`p_i`$’s are non-zero. Without loss of generality, we can assume that $`p_1+p_2+p_32n_1`$. Since $`2n_1<p_1+p_2+p_3+1(\frac{n_1}{2}+1)+2(n_11)+1<3n_1`$, we can write that $`p_1+p_2+p_3+1=2n_1+r`$, where $`0<r<n_1`$. Then $`p_1=2n_1+r(p_2+p_3+1)2n_1+r2(n_11)1=r+1`$. Hence $`1rp_11`$. Thus the loop family corresponding to $`p_1`$ have two (non-level) edges with the same label $`r`$, and so the family contains an $`S`$-cycle or a generalized $`S`$-cycle. This is impossible when $`G_1`$ is of type $`𝒫`$. When $`G_1`$ is of type $`𝒮`$, $`G_2`$ contains an $`S`$-cycle, so $`M(\gamma _1)`$ must be of type $`𝒫`$, a contradiction again. ∎

Finally we give an example realizing the case $`\mathrm{\Delta }=3`$ in Theorem 1.3. Let $`M`$ be the manifold obtained from the Whitehead link exterior by Dehn filling one component with slope $`6`$. Then $`M`$ is hyperbolic \[BZ1, p.286\] and $`M(1)=L(2,1)\mathrm{}L(3,1)`$. Since $`M`$ contains a once-punctured Klein bottle whose boundary has slope $`4`$, $`M(4)`$ contains a Klein bottle hitting the attached solid torus $`V`$ once. Also, the boundary torus of a neighborhood of the Klein bottle in $`M(4)`$ is known to be incompressible. Clearly, this torus meets $`V`$ twice. (If $`M(4)`$ contains a torus meeting $`V`$ once, then such a torus is non-separating in $`M(4)`$. This is impossible, because $`H_1(M(4))`$ is finite.)


format: text

text:
# Global Snapshot of Protein Interaction Network – A Percolation Based Approach

## I Introduction

Recent availability of a large amount of data from high-throughput experiments Zhu2 ; Uetz ; Ito ; Gavin ; Ho  has brought about a fundamental change in the way we study biological systems. Unlike the traditional methods which relied on probing a single or a few proteins to identify important pathways, it is now becoming possible to describe larger functional ‘modules’ Hartwell  and even the global properties of the entire proteome Jeong ; Maslov ; Mering ; Bader . Researchers are attempting to connect large-scale protein interaction data with information from phenotype studies Jeong ; Maslov . In one such analysis of data from yeast, Jeong et al. observed the connectivities of individual proteins in the network to closely follow a power-law distribution. Similar to other power-law networks, positive correlation existed between a protein’s inviability and its connectivity Jeong . In another study, Maslov et al. observed interesting patterns in the distribution of the links between the nearest neighbors in the network and postulated that such patterns give rise to the specificity and the robustness of the network Maslov .

One of the shortcomings of the previous approaches is that they drew conclusions about the global nature of the network from its local connectivity properties. It is unclear whether such local studies based on individual nodes or nearest neighbors fully capture the global picture of the network. For example, some essential proteins, namely, those for which null mutants produce inviable strains YeastDel , may have few numbers of direct links but still take important roles in the network through the proteins to which they are connected. Such proteins would not be correctly identified by just counting the number of links as in Ref. Jeong . To properly recognize such cases, it is necessary to go beyond the nearest neighbor links. However, it is not clear that the techniques mentioned above can easily be extended to answer such questions.

In this paper, we introduce a stochastic method inspired by the percolation model in statistical mechanicspercolation  that overcomes the shortcomings of the previous approaches. This method allows us to define a quantity that measures the correlation between any two nodes in the network, taking the topology of the entire network into account. Biologically, such correlations describe the direct and indirect influences of one protein on another through the protein interaction network. If such correlations indeed carry biological significance, we expect the essential proteins to be highly correlated, in general, with the rest of the network. One of our main results is that most essential proteins do possess higher correlations between themselves and the rest of the network. This is consistent with previous results Jeong , because in the first order, the correlations computed by us are proportional to the connectivities of the proteins. However, we show that it is important to go beyond the first order. Identifying essential proteins by our method performs consistently better than just counting links. Additionally, we observe that the essential proteins interact more tightly with the other essential proteins, thus forming a ‘network core’. This directly agrees with large-scale experiments probing protein networks Gavin .

Based on our method, we can also quantify the relative significance of an interaction to the integrity of the network. We observe that the interaction data from different measurement techniques, such as immunoprecipitation(IP) and the two-hybrid test, give distinct distributions. This suggests that various experimental techniques for probing the protein interaction might explore different regions of the network.

## II Method and Materials

### II.1 Bond-percolation on Graph

Given any two nodes in a network, the strength of their connectivity can be estimated in different ways. Some of these measures are local. For example, we can ask whether any two nodes are directed linked, how many common neighbors they share Samanta , etc. We can also ask how local properties of a node, such as the degree of links, associate with its function and its importance in the networkJeong . Furthermore, information about the correlations between nodes involving nonlocal properties, such as the length of the shortest path and clustering structures, will enable us to uncover hidden features buried within the massive data. Here, we present a generic approach that extracts useful information about a node beyond its local connections.

Correlations between two nodes may come from other numerous short paths rather than just the shortest path. A reasonable estimate of correlation should take into account the number and lengths of different paths between two nodes. One possible way to estimate such correlation between two nodes is to repeatedly remove some fraction $`q`$ of the links in the network chosen randomly and check whether they still remain connected. Their probability remaining connected is proportional to the number of short paths between them and inversely proportional the length of those paths. This probability provides a good measurement of the correlation between two nodes that includes the information regarding the non-local topology of the network. The described process of finding the correlation between two nodes in a network is equivalent to the bond-percolation model in statistical mechanicspercolation .

Mathematically, a network is treated in the language of graph theory, where a node is denoted as a vertex and a link as an edge. Given a graph $`G`$ with vertices $`V`$ and edges $`E`$, a percolation configuration is realized as follows. Each edge $`e_{ij}`$ linking vertices $`i`$ and $`j`$ is assigned a random number $`p_{ij}`$ distributed uniformly from 0 to 1. If this random number is greater than $`p=1q`$, a given percolation probability, then the edge is eliminated from the original graph. The final graph $`G^{}`$ consists of the edge set $`E^{}=E\overline{E}`$, where $`\overline{E}`$ is the set of edges that $`p_{ij}>p`$ and $`E^{}`$ consists those edges with $`p_{ij}<p`$. Assuming that $`G`$ is connected, the reduced graph $`G^{}`$ may or may not remain a single connected component depending on $`p`$.

### II.2 Susceptibility

The first step in applying the algorithm is to determine the appropriate value of the probability $`p`$. If $`p`$ is near one, then we only produce totally connected graphs. If $`p`$ is too close to zero, then the network is split into individual vertices and small clusters. An intermediate value of $`p`$ provides information about the non-local properties of the network.

The degree of fragmentation in the graph $`G^{}`$ can be quantified by the order parameter $`m(p)`$, the ratio of the largest connected component to the total graph size. It is defined as $`m(p)=N_{\mathrm{max}}/|V|`$, where $`N_{\mathrm{max}}`$ is the number of vertices of the largest connected component and $`|V|`$ is the total number of vertices. For a connected graph $`G`$, $`m(p)`$ varies from $`1/|V|`$ to 1 as $`p`$ changes from 0 to 1. Here, $`m`$ is a stochastic variable, whose fluctuation is defined by

$$\chi (p)=(mm)^2^{\frac{1}{2}}$$
(1)
The brackets denote the ensemble average, which is the average over many different realizations of $`G^{}`$. The curve of $`\chi (p)`$ reveals certain aspects of the graph topology. For example, if $`G`$ is a regular two dimensional square lattice, then $`\chi `$ diverges with a power law behavior as a function of $`pp_\mathrm{c}`$, for $`p_\mathrm{c}=1/2`$. For other types of regular lattices, like triangular lattices or higher dimensional lattices, $`p_\mathrm{c}`$ and/or the power law exponent also change. A maximum in $`\chi (p)`$ occurs at the transition point $`p_\mathrm{c}`$, indicating a phase transition and critical behaviorpercolation . At this critical point, the distribution of the sizes of the connected clusters decay as a power law. Chosing a value of $`p`$ near this critical value, we get the most non-local information regarding the network.

### II.3 Correlations and the definition of $`v_i`$

Whether two arbitrary vertices $`i`$ and $`j`$ remain connected in $`G^{}`$ can provide more detailed information about $`G`$. If two vertices retain their connection, it means that there exist paths in $`E^{}`$ from vertex $`i`$ to vertex $`j`$. Define $`\delta _{ij}`$ as function of a pair of vertices $`i`$ and $`j`$ such that $`\delta _{ij}=1`$ if vertices $`i`$ and $`j`$ are connected, and $`\delta _{ij}=0`$ otherwise. The percolation correlation $`c_{ij}`$ is then defined as the ensemble average of $`\delta _{ij}`$,

$$c_{ij}=\delta _{ij}.$$
(2)
With knowledge of the $`c_{ij}`$, we are equipped to measure how strongly a vertex $`i`$ links to the rest of the network counting both direct and indirect connections to vertex $`i`$. We define the quantity $`v_i`$ for vertex $`i`$,

$$v_i=\frac{1}{|V|}\underset{jV}{}c_{ij}$$
(3)
This value is sensitive not only to the linking degree at each vertex but also to higher order connections between a vertex and the rest of the random graph. Thus, $`v_i`$ effectively ranks the importance of a vertex in the graph. Intuitively, $`v_i`$ may be interpreted as the fraction of other vertices to which vertex $`i`$ remains linked, if each edge is broken with probability $`q=1p`$ in the graph $`G`$. In Fig. 1, we show the descending ranking order of the $`v_i`$’s for a small graph.

### II.4 The definition of $`\beta _{ij}`$

Using a similar idea, we can define a quantity that allows us to check the influence of an edge on the graph integrity. The elimination of some edges may fundamentally change the connectivity properties whereas the graph topology may be relatively unchanged against the deletion of others. For example, for a small fully connected subgraph, termed a clique, removal of a certain number of edges between the vertices of the subgraph tends not to separate the graph into disconnected pieces. Individual links in the subgraph do not play crucial roles in supporting the integrity of the subgraph and the whole graph. We define the quantity $`\beta _{ij}`$ to monitor the importance of edge $`e_{ij}`$ to the integrity of the graph,

$$\beta _{ij}=\frac{1}{|V|^2}\underset{l,mV}{}\left(c_{lm}\left(G^{}\{e_{ij}\}\right)c_{lm}\left(G^{}\{e_{ij}\}\right)\right).$$
(4)
The first term in the summation is correlation $`c_{lm}`$ measured by adding $`e_{ij}`$ in $`G^{}`$ independent of $`p_{ij}`$ and $`p`$. The second term in $`c_{lm}`$ measured by removing $`e_{ij}`$ in $`G^{}`$. The difference in measurement of $`c_{lm}`$ under the presence or absence of edge $`e_{ij}`$ allows us to distinguish edges. For example, if $`e_{ij}`$ bridges two clusters, then $`\beta _{ij}`$ will be elevated (note the edges 1, 2 and 3 in Fig. 1). Suppose edge $`e_{ij}`$ connects two disjoint connected components $`A`$ and $`B`$ with sizes $`n_\mathrm{A}`$ and $`n_\mathrm{B}`$. Then, in a realization of $`G^{}`$, the contribution to $`\beta _{ij}`$ is the difference between $`_{l,mAB}\delta _{lm}=|n_A+n_B|^2`$ and $`_{l,mA}\delta _{lm}+_{l,mB}\delta _{lm}=|n_A|^2+|n_B|^2`$. Namely, the contribution to $`\beta _{ij}`$ is proportional to $`n_\mathrm{A}n_\mathrm{B}`$. However, if $`e_{ij}`$ is embedded within a connected component such that adding or removing $`e_{ij}`$ does not perturb the component’s connectivity, then $`e_{ij}`$ is redundant and does not contribute to $`\beta _{ij}`$. With this interpretation, $`\beta _{ij}`$ measures how well $`e_{ij}`$ succeeds in connecting differing big components or modules.

### II.5 Protein interaction data

Here, we apply the described method on the yeast protein interaction data taken from the Database of Interacting Proteins(DIP) Deane . The dataset contains 14871 interactions between 4692 proteins111We used the files “yeast20020901.lst” and “dip20020616.xin”, downloaded from DIP database (http://dip.doe-mbi.ucla.edu/). and includes interactions measured by different experimental methods. We treat the interaction network as an undirected graph, with the proteins as vertices. If two proteins are interaction partners in the dataset, the corresponding vertices are joined by an edge.

## III Results and Discussions

### III.1 Determination of $`p`$

As a first step in applying this stochastic method on the protein interaction network, we need to determine the appropriate value of $`p`$. If $`p`$ is near one, then we will only produce totally connected graphs. If $`p`$ is too close to zero, then we will only obtain information about small clusters. Some intermediate value of $`p`$ will give us global properties of the network.

In order to determine the proper value of $`p`$, we need to compute the curve $`\chi (p)`$. Such a curve for the DIP data is shown in Fig. 2. The curve peaks at about $`p=0.07`$, where the size fluctuations of the largest cluster are maximal. Most realizations of the percolation graph $`G^{}`$ in the neighborhood of this peak yield sparse but still predominantly connected graphs. Accordingly, computing $`v_i`$ and $`\beta _{ij}`$ around this peak in $`\chi (p)`$ avoids the finite size effect at smaller $`p`$ and loss of resolutions at larger $`p`$.

### III.2 Distribution of $`v_i`$

We gathered our data from $`10^5`$ realizations of the graph at $`p=0.07`$. The distribution of $`\mathrm{log}(v_i)`$ for the protein interaction network is shown in Fig. 3. We also report the distributions of a subset composing only the essential proteins222We got the list of essential proteins from the Saccharomyces Genome Deletion Project YeastDel  (http://yeastdeletion.stanford.edu/).. The distribution of $`v_i`$ for essential proteins significantly differs from the background distribution and is biased toward greater $`v_i`$. A protein with a greater $`v_i`$ ties to the network more strongly than a protein possessing a smaller $`v_i`$. Therefore, we would predict that removing a protein from yeast with a greater $`v_i`$ harms more biologically important pathways and would thereby be more likely to destroy viability. The percentage of proteins having a given $`v_i`$ which are essential ( (number of essential proteins of a given $`v_i`$)/(number of proteins of the given $`v_i`$) ) is shown in Fig. 4. This percentage has strong positive correlation with $`v_i`$, in agreement with the prediction.

What are the specific connectivity properties that produce a large $`v_i`$ for a specific protein? To a first order approximation, $`v_i`$ is proportional to the degree of connectivity of the $`i^{\mathrm{th}}`$ protein. Since a protein with $`k`$ interactions is usually connected to at least $`pk`$ proteins, in the first order $`v_i`$ is proportional to $`k_i`$. However, the protein interaction network displays small world properties333The graph diameter (the maximum amongst all the shortest paths between all pairs of vertices) of the protein interaction network is 12. The average path length of the path between any two proteins is 4.23., Therefore, the correction to $`v_i`$ from higher order connections should be included. For example, if the number of next-nearest neighbors of a protein is much greater than the number of nearest neighbors, then the contribution from the next-nearest neighbors is comparable to that of the nearest neighbors. In such a case, the proteins with the same $`k_i`$ have a broad distribution of $`v_i`$ as in our results. The value of $`v_i`$ gives more extensive information about the protein’s connectivity in the network beyond that of its nearest neighbors.

Our method is advantageous because we can identify important proteins that might otherwise not be considered significant because they have lower first-order interaction degree. Such proteins probably control other essential proteins through a few critical interactions. To illustrate the power of this approach compared to merely counting the nearest neighbor degree of interactions, we rank the proteins by $`v_i`$ and compare the result to the ranking by $`k_i`$ (see Table 1). For example, 61% of the proteins in the top 2% of $`v_i`$ are essential, whereas only 52% of the proteins in the top 2% of $`k_i`$ are required for viability. Such a result suggests the essential proteins with higher $`v_i`$ not only have more interactions but are also more likely to interact more frequently with other proteins, which also tend to be essential. A similar observation has been reported by Gavin, et al. Gavin , and our independent evidence supports their hypothesis.

The proteins with 10 highest $`v_i`$ are listed in Table 2. The full list of proteins with their $`v_i`$ can be found in the supplemental web site444http://www.nas.nasa.gov/Groups/SciTech/nano/msamanta/projects/percolation/index.php. A selection of a few essential proteins with high $`v_i`$ but low $`k_i`$ is also shown in Table 3.

### III.3 Distribution of $`\beta _{ij}`$

The interactions in the network can be grouped by the experimental methods used to detect them. We score each interaction within the network by $`\beta _{ij}`$. The distribution of $`\mathrm{log}(\beta _{ij})`$(Fig. 5) provides a mechanism to detect differences amongst different subsets of interactions obtained by varied experimental methods. In Fig. 5, we compare the distribution of $`\mathrm{log}(\beta _{ij})`$ from the whole network to distribution derived from several subsets of the network. First, we use the subset, as the core set, of the interactions that was derived by Deane et al. Deane . Interactions in the core set are statistically verified to reduce the false positive rate, yielding 1925 interactions (excluding self-interacting pairs). The distribution of $`\mathrm{log}(\beta _{ij})`$ for the core set is similar to that obtained for the entire network. However, upon comparing the distribution of $`\mathrm{log}(\beta _{ij})`$ for subsets of those interactions obtained from different experimental procedures, differences emerge. For example, interactions measured by immunoprecipitation tends to have a larger $`\beta _{ij}`$, so that the distribution of $`\mathrm{log}(\beta _{ij})`$ of this subset shifts to the right. In contrast, the distribution for the subset of interactions measured with high-throughput two-hybrid tests display the opposite trend.

If $`e_{ij}`$ is the only edge linking two clusters, the contribution of a particular realization of the percolation procedure to $`\beta _{ij}`$ is proportional to the product of the sizes of the two clusters. Hence, an edge with a greater $`\beta _{ij}`$ has a greater tendency to link two large modules or clusters in the network. With this notion in mind, an examination of Fig. 5 suggests that the IP method is possibly more sensitive to interactions between proteins in different large modules while the two-hybrid tests are better suited to detecting interactions which tend not to link larger modules.

The discrepancy between the IP method and the two-hybrid tests might reflect the underlying biochemical differences between the two methods. Unlike IP, the two-hybrid test is an in vivo technique, and thus it can detect transient and unstable interactionsMering . Our analysis of the distribution of $`\mathrm{log}(\beta _{ij})`$ for the two-hybrid data is a quantitative demonstration that these transient and unstable interactions contribute less to the integrity of the interaction network.

## IV Conclusion

We presented a stochastic algorithm that explored the global connectivity properties of a protein interaction network. This percolation-based algorithm allowed us to assign weights to vertices and edges according to non-local topological properties. We applied the algorithm to the protein interaction network for yeast and found that the percentage of essential proteins correlated strongly with $`v_i`$. Importantly, the values of $`v_i`$, which incorporated the knowledge of connections beyond the nearest neighbors, could more successfully discriminate essential proteins than a method based solely on local connections. In addition, the essential proteins with greater $`v_i`$ not only possessed more interactions with any other proteins but also displayed more interactions with other essential proteins. This result suggested that essential proteins along with other proteins having greater $`v_i`$ might form a “core network” with a higher density of interactions within the “core network” than the background network. If this unverified hypothesis is confirmed, then we would gain significant insight into the evolution of a protein interaction network. Are the proteins in this “core network” in general more evolutionarily conserved than others? Hunter et al. claimed that there is significant negative correlation between each protein’s degree of connectivity and protein evolutionary rate, and that evolutionary change may occur largely by coevolution Fraser . If this is indeed so, we expect a stronger correlation between $`v_i`$ and protein evolutionary rate, since $`v_i`$ provides a better resolution than the degree of connectivity for proteins’ positions in their interaction network.

The $`\beta _{ij}`$ scores for interaction could distinguish the differences between different experimental methods for measuring protein interactions. Such a quantitative measure of the distinction amongst the experimental approaches will aid the interpretation of the proteomic data.

In principle, $`c_{ij}`$ can be calculated exactly given a percolation probability $`p`$. However, this would require recursive iterations over all possible sub-graphs. Our stochastic approach efficiently obtains the approximations to the exact value of $`c_{ij}`$, $`v_i`$ and $`\beta _{ij}`$. In this work, we model the interaction network as a static graph with uniform weight on each edge. For a biological system, dynamical aspects need to be incorporated. Various experimental methods for probing the physical interactions between proteins respond differently to the dynamics of biological systems. The two-hybrid test is more sensitive to transient interactions while the IP method is more sensitive to large and stable protein complexes. The differences might be addressed from different dynamics aspects in the interaction network.

With regard to future pursuits, we note that it is also possible to use $`\beta _{ij}`$ to cluster vertices within a random graph. The $`\beta _{ij}`$ score for a random graph is similar to the edge “betweenness”, defined as the number of shortest paths between all pairs of vertices passing through a given edge. An edge with a greater $`\beta _{ij}`$ is likely also an edge with a greater edge “betweenness”, because such an edge has great tendency to bridge two different clusters or modules. Clustering utilizing edge “betweenness” have been successfully applied to certain types of random networksNewman . We expect that results similar to those shown in Fig. 1 could be achieved with $`\beta _{ij}`$ not only for this small test graph but more significantly for larger graphs in which the computational cost of calculating edge “betweenness” is prohibitive. For the present, however, the idea of percolation on random networks provides a natural mechanism for revealing dominant cluster structure within a graph. We hope such natural cluster structure will provide further details about the protein interaction network.

###### Acknowledgements.

We thank Hao Li and Shoudan Liang for fruitful discussion. C. S. Chin also likes to thank Yigal Nochomovitz for critical reading of the manuscript. C. S. Chin is supported by Sandler Opportunity Grant. M. P. Samanta is supported by NASA contract DTTS59-99-D-00437/A61812D to CSC.