5.1 SPQRK trees

The SPQR tree of a 2-connected graph G is a tree that displays all the 2-separations of G. Since we need to consider graphs that are not necessarily 2-connected, we use a variant of the SPQR tree that we call the SPQRK tree.

Let G be a connected graph. The SPQRK tree $T_G$ of G is a tree, where each node $a\in V(T_G)$ is associated with a multigraph $H_a$ which is a minor of G. Each vertex $x \in V(H_a)$ is a vertex of G, that is, $V(H_a) \subseteq V(G)$ . Each edge $e \in E(H_a)$ is classified either as a real or virtual edge. By the construction of an SPQRK tree, each edge $e\in E(G)$ appears in exactly one minor $H_a$ as a real edge, and each real edge $e\in E(H_a)$ is an edge of G. The SPQRK tree $T_G$ is defined recursively as follows.

1. 1. If G is 3-connected, then $T_G$ consists of a single R-node a with $H_a \;:\!=\; G$ . All edges of $H_a$ are real in this case.

2. 2. If G is a cycle, then $T_G$ consists of a single S-node a with $H_a \;:\!=\; G$ . Again, all edges of $H_a$ are real in this case.

3. 3. If G is isomorphic to $K_1$ or $K_2$ , then $T_G$ consists of a single K-node a with $H_a \;:\!=\; G$ . Again, all edges of $H_a$ are real in this case.

4. 4. If G is 2-connected and has a cutset $\{x,y\}$ such that the vertices x and y have degree at least 3, we construct $T_G$ inductively as follows. Let $C_1,\dots, C_r$ ( $r\geqslant 2$ ) be the connected components of $G - \{x,y\}$ . First add a P-node a to $T_G$ , for which $H_a$ is the graph with $V(H_a)\;:\!=\;\{x,y\}$ consisting of r parallel virtual edges and one additional real edge if xy is an edge of G.Next let $G_i$ be the graph $G[V(C_i)\cup \{x,y\}]$ with the additional edge xy if it is not already there. Since we include the edge xy, each $G_i$ is 2-connected and we can construct the corresponding SPQRK tree $T_{G_i}$ by induction. Let $a_i$ be the (unique) node in $T_{G_i}$ for which xy is a real edge in $H_{a_i}$ . In order to construct $T_G$ , we make xy a virtual edge in the node $a_i$ and connect $a_i$ to a in $T_G$ .

5. 5. If G has a cut-vertex x and $C_1, \dots, C_s$ ( $s\geqslant 2$ ) are the connected components of $G - x$ , then construct $T_G$ inductively as follows. First, add a Q-node a to $T_G$ , for which $H_a$ is the graph consisting of the single vertex x. For each $i \in [s]$ , let $G_i \;:\!=\; G[V(C_i)\cup \{x\}]$ . Since $G_i$ is connected, we can construct the corresponding SPQRK tree $T_{G_i}$ by induction. If there is a unique node $b_i \in V(T_{G_i})$ such that $x \in V(H_{b_i})$ , then make a adjacent to $b_i$ in $T_{G}$ . If x is in at least two nodes of $V(T_{G_i})$ , then $x \in V(C) \cap V(D)$ for some $(\leqslant 2)$ -separation (C,D) of $G_i$ . Since $G_i - x$ is connected, there must be a P-node $b_i$ in $T_{G_i}$ such that $x \in V(H_{b_i})$ . Note that $b_i$ is not necessarily unique. Choose one such $b_i$ and make a adjacent to $b_i$ in $T_G$ .

As a side remark, note that the SPQRK tree $T_G$ of G is in fact not unique—there is some freedom in choosing $b_i$ in the last point in the definition above—however, for our purposes we do not need uniqueness, we only need that $T_G$ displays all the $(\leqslant 2)$ -separations of G.

The next lemma is the crux of the proof. Let J and G be graphs and X and Y be cliques in J and G, respectively, with $|X|=|Y|$ . Let $\phi\;:\;V(J) \to V(G)$ be an image of J in G. We say that $\phi$ fixes X at Y if $\phi(X)=Y$ . Let $(J', \mathcal P)$ be a partially subdivided graph such that $J=J'/ \mathcal P$ . We call $uv \in E(J)$ a fake edge if u and v are the set of ends of some $P \in \mathcal P$ . Otherwise, uv is a true edge.

Let X be a clique in J such that:

1. 1. there do not exist independent flaps (A,B) and (C,D) of J with $X \subseteq V(B \cap D)$ ,

2. 2. $|X| \in \{1,2\}$ , and if $|X|=2$ , then X is a true edge,

3. 3. if $|X|=1$ and $J \cong P_3$ , then e is a true edge, where e is the unique edge of J not incident to X,

4. 4. if $|X|=1$ and $J \cong C_3$ , then e is a true edge, where e is the unique edge of J not incident to X,

5. 5. if $|X|=2$ and $J \cong C_4$ , then e is a true edge, where e is the unique edge of J not incident to a vertex of X,

6. 6. if J is 3-connected, then all edges of J with neither end in X are true,

7. 7. if (A,B) is a flap of J, with $X \subseteq V(B), |V(A \cap B)|=1$ , and $A \cong P_3$ , then e is a true edge, where e is the unique edge of A not incident to $V(A \cap B)$ ,

8. 8. if (A,B) is a flap of J, with $X \subseteq V(B), |V(A \cap B)|=1$ , and $A \cong C_3$ , then e is a true edge, where e is the unique edge of A not incident to $V(A \cap B)$ ,

9. 9. if (A,B) is a flap of J, with $X \subseteq V(B), |V(A \cap B)|=2$ , and $A^+ \cong C_3$ , then at least one e or f is a true edge, where e and f are the two edges of A with an end not on $V(A \cap B)$ .

10. 10. if (A,B) is a flap of J, with $X \subseteq V(B), |V(A \cap B)|=2$ , and $A^+ \cong C_4$ , then e is a true edge, where e is the unique edge of A not incident to $V(A \cap B)$ ,

11. 11. if (A,B) is a flap of J such that $A^+$ is 3-connected, then all edges of A with neither end in $V(A \cap B)$ are true.

Then for every n-vertex graph G embeddable in $\Sigma$ and every clique Y in G with $|Y|=|X|$ , there are at most $c_{5.1}(j,g) n$ images of $J' - \mathcal P$ in G with X fixed at Y that extend to an image of J’ in G.

Proof. Let G be an n-vertex graph embedded in a surface $\Sigma$ of Euler genus g and Y be a clique in G with $|Y|=|X|$ . We begin by proving the lemma when J is small. The lemma clearly holds if $|V(J)|=1$ or $|V(J)|=2=|X|$ . If $|V(J)|=2$ and $|X|$ =1, let y be the vertex of J not in X. Since there are at most $n-1$ vertices of G to send y to, we are done. Similarly, we are done if $J \in \{P_3, C_3\}$ and $|X|=2$ . If $J \in \{P_3, C_3\}$ and $|X|=1,$ let e be the unique edge of J not incident to X. Note that e exists in the case that $J \cong P_3$ , since the vertex in X cannot be the middle vertex of J by (1). By (3) and (4), e is a true edge, so there are at most $|E(G)| \leqslant 3(g+1)n$ edges of G to send e to. Each edge gives at most two images of $J' - \mathcal P$ with X fixed at Y in G, so there are at most $6(g+1)n$ such images. Suppose that $|V(J)|=4$ . Note that $J \not\cong P_4$ , by (1). If $J \cong C_4$ , then $|X| =2$ by (1). Let e be the unique edge of J not incident to a vertex of X. By (5), e is a true edge, so again there are at most $3(g+1)n$ edges of G to send e to. Each edge gives at most four images of $J' - \mathcal P$ with X fixed at Y in G, so there are at most $12(g+1)n$ such images.

In summary, by the above discussion we may assume that $|V(J)|\geqslant 4$ , and $J \not\cong P_4, C_4$ in case $|V(J)|=4$ .

Let $T_J$ be the SPQRK tree of J. Suppose that $V(T_J)=\{a\}$ . If a is a K-node, then we are done since $|V(J)| \leqslant 2$ . If a is an S-node, then by (1), $J\cong C_3$ or $J\cong C_4$ , so we are done. By the preceding remarks, we may assume that J is 3-connected, or $|V(J)| \geqslant 4$ and $|V(T_J)| \geqslant 2$ . A clique X’ of J is a true clique if $|X'|=1$ , or $|X'|=2$ and the edge of X’ is a true edge. If J is 3-connected, we have the following easy claim.

Proof. Since J is 3-connected, there is an edge X’ of J with neither end in X; otherwise, X is a cutset of J with $|X| \leqslant 2$ . By (6), X’ is a true edge. Since J is 3-connected, we are done by Menger’s theorem.

We now suppose that $|V(J)| \geqslant 4$ and $|V(T_J)| \geqslant 2$ , and we prove that Claim Theorem 5.2 also holds in this case. Let W be the set of K-, S-, and R-nodes of $V(T_J)$ . Note that for each $a \in W$ , $H_a$ is a subgraph of J. If U is a non-empty proper subset of W, we define $H_U \;:\!=\; \bigcup_{a \in U} H_a$ , $bd(U) \;:\!=\; V(H_U \cap H_{W \setminus U})$ , $\lambda(U) \;:\!=\;|bd(H_U)|$ , and $sep(U)\;:\!=\;(H_U, H_{W \setminus U})$ .

Proof. Since $|V(T_J)| \geqslant 2$ , $T_J$ has at least two leaves. For each leaf a of $T_J$ , there is a flap $(C^a, D^a)$ such that $V(C^a)=V(H_a)$ . Since $(C^a, D^a)$ and $(D^a, C^a)$ are independent flaps, exactly one of $(V(C^a) \setminus V(D^a)) \cap X$ or $(V(D^a) \setminus V(C^a)) \cap X$ is non-empty by (1). Thus, $T_J$ has exactly two leaves and there is a leaf $\ell$ of $T_J$ such that $X \subseteq V(H_\ell)$ and $X \setminus bd(\{\ell\}) \neq \emptyset$ .

Proof. Towards a contradiction, suppose that $\lambda(U) \leqslant 2$ for some non-empty $U \subseteq W \setminus \{\ell, r\}$ which is not a single K-node. Let $(C^r, D^r)$ be the flap of J such that $V(C^r)=V(H_r)$ . Since $X \subseteq V(H_\ell)$ , $(C^r, D^r)$ and sep(U) are independent flaps of J which contradict (1).

Proof. Since $|V(J)| \geqslant 4$ , for each $s \in S$ , $(\delta(s), J - s)$ is a flap with $X \subseteq V(J - s)$ , where $\delta(s)$ is the subgraph of J induced by the edges incident to s. Thus, by (1), S is a clique in J, and therefore, $|S| \leqslant 3$ . Moreover, $|S|=3$ is impossible, since $|V(J)| \geqslant 4$ and J is connected. Thus, $|S| \leqslant 2$ . Since $(A,B)=sep(\{r\})$ is a flap with $X \subseteq V(B)$ , (1) also implies $S \subseteq V(H_r)$ .

Proof. Let c and d be distinct cut-vertices of J. Let $W_{cd} \subseteq W$ be the set of K-, S-, and R-nodes of $V(T_J)$ strictly between the Q-nodes corresponding to c and d in $T_J$ . Note that $sep(W_{cd})$ is a 2-separation of J, unless $W_{cd}$ is just a single K-node. Moreover, if $W_{cd}$ is not a single K-node, then $sep(\{r\})$ and $sep(W_{cd})$ would contradict (1). It follows that J has at most two cut-vertices and that $\{c,d\}$ is the vertex set of some K-node of $T_J$ .

Proof. If r is an R-node, then all edges of $H_{r}^-$ are true by (11). In this case, we let X’ be any edge of $H_{r}^-$ such that $X' \cap bd(\{r\})=\emptyset$ . If r is an S-node, then by (1), either $H_r \cong C_3$ , or $H_r \cong C_4$ and $|bd(\{r\})|=2$ . In either case, by (8), (9), and (10), we can choose X’ to be a true edge such that $V(H_r) \setminus (X' \cup bd(\{r\})) = \emptyset$ . Lastly, suppose that r is a K-node. Then $H_r \cong K_2$ , say $H_r$ consists of the edge uv with $v \in bd(\{r\})$ . If $v \notin S$ , we let $X'\;:\!=\;\{u\}$ . If $v \in S$ , we let $X'\;:\!=\;\{u,v\}$ ; note that uv is a true edge by (7) in this case.

Suppose the claim is false for the above choice of X’ for some vertex $w \in V(J) \setminus (X \cup X')$ , and let $X^+\;:\!=\;X \cup X'$ . Note that $|X^+| \geqslant 3$ by our choice of X’, since if $|X|=1$ then J is 2-connected by (1). (Indeed, if J is not 2-connected then J has a flap (A,B) that is a 1-separation with $X \subseteq B$ , but then $(B, A \cup X)$ is also a flap, contradicting (1).) Thus, by Menger’s theorem, there is a $({\leqslant}\,2)$ -separation $(J_1,J_2)$ of J with $w \in V(J_1) \setminus V(J_2)$ and $X^+\;:\!=\;X \cup X' \subseteq V(J_2)$ .

Let a be an S-node of $T_J$ . Observe that every 2-separation of the cycle $H_a$ lifts to a 2-separation of J. We say that a 2-separation of J is rooted at a if it is a lift of a 2-separation of $H_a$ . Since the SPQRK tree $T_J$ of J ‘displays’ all the $(\leqslant 2)$ -separations of J, every $(\leqslant 2)$ -separation (A,B) of J

• is equal to sep(U) for some $U \subseteq W$ , or

• is rooted at some S-node a of $T_J$ , or

• is obtained from a 1-separation (A’,B’) by adding an isolated vertex to A’ or B’ (which is thus in $A \cap B$ ).

Suppose $(J_1, J_2)=sep(U)$ for some $U \subseteq W$ . Since $X^+ \subseteq V(J_2)$ , $X \setminus bd(\{\ell\}) \neq \emptyset$ , and $X' \setminus bd(\{r\}) \neq \emptyset$ , we have $U \subseteq W \setminus \{\ell, r\}$ . This is a contradiction since $\lambda(U) \geqslant 3$ by Claim Theorem 5.4. Similarly, $(J_1, J_2)$ cannot be rooted at an S-node, unless $\deg_J(x)=2$ for some $x \in V(J_1) \setminus V(J_2)$ . However, by Claim Theorem 5.5 and our choice of X’, $\deg_J(x) \geqslant 3$ , for all $x \in V(J) \setminus X^+$ , so this is also impossible.

Finally, suppose the third possibility holds for some 1-separation (A’,B’) of J. Observe that every 1-separation (A,B) of J has $X' \subseteq V(A)$ and $X \subseteq V(B)$ ; or $X \subseteq V(A)$ and $X' \subseteq V(B)$ . By swapping the order of (A’,B’), we may assume that $X' \subseteq V(A')$ and $X \subseteq V(B')$ . Moreover, $(A',B' \cup \{a\}) \in \{(J_1, J_2), (J_2, J_1)\}$ for some $a \in V(A') \setminus V(B')$ ; or $(A' \cup \{b\}, B') \in \{(J_1, J_2), (J_2, J_1)\}$ for some $b \in V(B') \setminus V(A')$ . If $(A' \cup \{b\}, B')=(J_1, J_2)$ , then (A’,B’) is a 1-separation of J such that $X \cup X' \subseteq V(B')$ . However, no such separation exists (by the proof that $(J_1, J_2) \neq sep(U)$ for all $U \subseteq W$ ). Similarly, $(A',B' \cup \{a\})=(J_2, J_1)$ is impossible. If $(A' \cup \{b\}, B')=(J_2, J_1)$ , then (A’,B’) and $(B', A' \cup \{b\})$ contradict (1). The reTheorem 1.2ing case is $(A', B' \cup \{a\})=(J_1, J_2)$ . Let c be the unique vertex in $V(A') \cap V(B')$ . Recall that by the choice of X’, if r is an R-node or an S-node, then $|X'|=2$ and $c \notin X'$ . However, this contradicts $X' \subseteq V(J_2)$ . Thus, r is a K-node. Note that $(A',B')=sep(\{r\})$ is impossible, because $V(A') \setminus (V(B' \cup \{a\}))$ would be empty, and hence, $(A',B' \cup \{a\})$ is not a 2-separation. Thus, $c \notin V(H_r)$ . Let v be the cut-vertex of J in $V(H_r)$ . By Claim 5.6, c and v are adjacent and $v \in S=\{s \in V(J) \setminus X \mid \deg_J(s) \leqslant 2\}$ . In this case, by our choice of X’, we have $|X'|=2$ and $c \notin X'$ , so we again have a contradiction.

Let X’ be the true clique of J given by Claim 5.2 or by Claim 5.7, depending whether J is 3-connected, or $|V(J)| \geqslant 4$ and $|V(T_J)| \geqslant 2$ . Suppose $|X'|=1$ . For each $y \in V(G)$ , let $c_y$ be the number of images of $J' - \mathcal P$ in G, with X fixed at Y and X’ fixed at y, that extend to an image of J’ in G. Suppose $|X'|=2$ . For each $f \in E(G)$ , let $c_f$ be the number of images of $J' - \mathcal P$ in G, with X fixed at Y and X’ fixed at f, that extend to an image of J’ in G.

We claim that if $|X'|=1$ then $c_y \leqslant c_{3.1}(j, c_{3.4}(j, 2g+3))$ for all $y \in V(G)$ , if $|X'|=2$ then $c_f \leqslant c_{3.1}(j, c_{3.4}(j, 2g+3))$ for all $f \in E(G)$ . We will prove both inequalities simultaneously, since the proof is the same. Arguing by contradiction, suppose y or $f\;:\!=\;uv$ is a counterexample, and set $Y^+=Y \cup \{y\}$ if $|X'|=1$ and $Y^+=Y \cup \{u,v\}$ if $|X'|=2$ . Then, there exists a collection $\mathcal J_1$ of more than $c_{3.1}(j, c_{3.4}(j, 2g+3))$ images of J’ in G with X fixed at Y and X’ fixed at y (respectively, X’ fixed at f) such that the restrictions of these images to $J' - \mathcal P$ are all distinct.

By Lemma 3.1, $\mathcal J_1$ contains a coherent subfamily $\mathcal J_2$ of size at least $c_{3.4}(j, 2g+3)$ . Let $\mathcal{V}$ be the collection of vertex sets of $\mathcal J_2$ . Note that by coherence, $|\mathcal V|=|\mathcal J_2| \geqslant c_{3.4}(j, 2g+3)$ . By Lemma 3.4, $\mathcal{V}$ contains an s-sunflower $\mathcal F$ , where $s \geqslant 2g+3$ . Let Z be the kernel of $\mathcal{F}$ . By construction, $Y^+ \subseteq Z$ . Let I be the set of internal vertices of all $P \in \mathcal P$ . Since the restrictions of each copy of J’ in $\mathcal F$ to $J' - \mathcal P$ are all distinct, for all $F \in \mathcal F$ there must be a vertex $w_F \in F \setminus Z$ such that $w_F$ is the image of a vertex in $V(J') \setminus I$ . By coherence, we may assume that each $w_F$ corresponds to the same vertex in $V(J') \setminus I$ . By Claims 5.2 and 5.7, there are three internally disjoint paths from $w_F$ to $Y^+$ in G[F] whose ends in $Y^+$ are distinct. For each $F \in \mathcal {F}$ , let $Z_F$ be the set consisting of the first vertices of Z on each of these three paths. By coherence, we may assume $Z_F$ is the same for all $F \in \mathcal {F}$ . Thus, G contains a subdivision of $K_{3, 2g+3}$ . However, this is impossible, since $K_{3, 2g+3}$ does not embed in $\Sigma$ .

It follows that $c_y, c_f \leqslant c_{3.1}(j, c_{3.4}(j, 2g+3))$ for all $y \in V(G)$ and $f \in E(G)$ . The proof is complete by summing over all possible $y \in V(G)$ if $|X'|=1$ , and summing over all possible $f \in E(G)$ if $|X'|=2$ .

The final ingredient we need is the following ‘flap reduction’ lemma.

• A has no isolated vertices, and

• there exists a flap (A,B) of H and a set $\mathcal F$ of k independent flaps in H with $(A,B) \in \mathcal F$ .

Then, $B^+$ has flap-number $k-1$ . Moreover, A is connected and $A^+$ does not contain independent flaps (C, D) and (C’,D’) such that $V(A \cap B) \subseteq V(D \cap D')$ .

Proof. We first show that $B^+$ has flap-number at least $k-1$ . To see this, let $\mathcal F$ be a set of k independent flaps in H such that $(A,B) \in \mathcal F$ . Every flap $(C,D) \in \mathcal F \setminus \{(A,B)\}$ corresponds to a flap (C, D’) in $B^+$ , unless $k=2$ , H is planar, and $\mathcal F=\{(A,B), (B,A)\}$ . In either case, $B^+$ has flap-number at least $k-1$ .

We now prove the upper bound. Towards a contradiction, let $(C_1, D_1), \dots , (C_k, D_k)$ be independent flaps in $B^+$ . Let $X\;:\!=\;V(A \cap B)$ . If $X \subseteq V(S)$ for a subgraph S of $B^+$ , we let $S +_X A$ be the subgraph of H obtained by gluing A to S along X, and deleting the edge between the ends of X in $B^+$ if the edge does not exist in H. If X is contained in $V(D_\ell)$ for every $\ell \in [k]$ , then $(A,B),(C_1, D_1 +_X A ), \dots , (C_k, D_k +_X A)$ are $k+1$ pairwise independent flaps in H. Thus, X is not contained in $V(D_\ell)$ for some $\ell \in [k]$ . By relabelling, we may assume $\ell=1$ . Since $(V(C_1) \setminus V(D_1)) \cap X \neq \emptyset$ and $(V(C_1) \setminus V(D_1)) \cap (V(C_i) \setminus V(D_i))=\emptyset$ for all $i > 1$ , we have $X \subseteq V(D_i)$ for all $i>1$ . Then, $(C_1 +_X A, D_1), (C_2, D_2 +_X A), \dots (C_k, D_k +_X A)$ are k independent flaps in H. Since A is a proper subgraph of $C_1 +_X A$ , this contradicts the maximality of A.

Finally, we show that the last sentence of the lemma holds. Suppose that A is disconnected and $A_1, \dots, A_c$ are the connected components of A. Since H is connected, $A_i$ contains a vertex of $V(A \cap B)$ for all $i \in [c]$ . Thus, $c=2$ and $A_1$ and $A_2$ each contain exactly one vertex of $V(A \cap B)$ . Since neither $A_1$ nor $A_2$ is an isolated vertex, there exist $B_1$ and $B_2$ such that $(A_1,B_1)$ and $(A_2,B_2)$ are independent flaps of H. Thus, $\mathcal F \setminus \{(A,B)\} \cup \{(A_1, B_1), (A_2, B_2)\}$ is a set of $k+1$ independent flaps of H, which contradicts that H has flap-number k. Similarly, $A^+$ does not contain independent flaps (C, D) and (C’,D’) such that $V(A \cap B) \subseteq V(D \cap D')$ .

We call a subgraph A of H a half-flap if (A,B) is a flap of H for some B. Two half-flaps A and C are independent if there exist B and D such that (A,B) and (C,D) are independent flaps. We say that A is a full-half-flap if A satisfies the conditions of Lemma 5.8.

We stress that the condition that A is maximal is essential in the definition of a full-half-flap. To see this, let H be the $2 \times k$ grid, for k large. Note that even though H has many 2-separations, the flap-number of H is 2. Moreover, the only full-half-flaps of H are $H-y$ , where y is one of the four degree-2 vertices of H. In this case, $B^+ \cong K_3$ , which has flap-number 1. Reducing on any other flap of H yields a graph that still has flap-number 2.

We now complete the proof of the upper bound in Theorem 1.2.

Theorem 5.9 Let $c_{5.9}(h,g)\;:\!=\;6(g+1)c_{4.1}(h,g)c_{3.2}(h,g)c_{5.1}(h, g+2)^h.$ Then for every graph H with h vertices and every surface $\Sigma$ of Euler genus g in which H embeds,

\begin{equation*}C(H,\Sigma, n) \leqslant I(H,\Sigma,n) \leqslant c_{5.9}(h,g)n^{f(H)}.\end{equation*}

Proof. Let $k\;:\!=\;f(H)$ . Since $c_{5.9}(h_1,g)\cdot c_{5.9}(h_2,g) \leqslant c_{5.9}(h,g)$ whenever $h_1+h_2=h$ , we may assume that H is connected by induction on $|V(H)|$ . A reduction sequence of H is a sequence of graphs $H_k, \dots, H_j$ for some $j \leqslant k$ , where $H_k\;:\!=\;H$ , and for all $i > j$ , $H_{i-1}\;:\!=\;B_i^+$ , where $(A_i, B_i)$ is a flap in $H_i$ satisfying the conditions of Lemma 5.8. By Lemma 5.8, every reduction sequence satisfies the following properties.

We now establish further properties of reduction sequences. Let $H_k, \dots, H_j$ be a reduction sequence of H, with corresponding flaps $(A_\ell, B_\ell)$ in $H_\ell$ . If $V(A_\ell) \cap V(B_\ell)\;:\!=\;\{u,v\}$ and $uv \notin E(H_\ell)$ , we declare uv to be a fake edge of $H_{\ell-1}$ . An edge of $H_\ell$ is a fake edge if it is a fake edge of $H_{\ell'}$ for some $\ell' \geqslant \ell$ , and it is a true edge if it is not a fake edge.

Proof. Let (C,D) be a flap of $H_\ell$ that is a counterexample with $|E(C)|-|V(D)|$ maximum. Let $X\;:\!=\;V(C \cap D)$ . Note that, by the maximality of $|E(C)|-|V(D)|$ , if $H_\ell$ contains an edge f whose ends are X, then $f \in E(C)$ . We claim that each $x \in X$ is incident to an edge of D. If not, then x must be an isolated vertex of D. But now, $(C, D-x)$ contradicts the maximality of $|E(C)|-|V(D)|$ . For all $i \in \{k, \dots, \ell+1\}$ set $X_i\;:\!=\;V(A_i \cap B_i)$ . Let $\mathcal I$ be the set of indices $i \in \{k, \dots, \ell+1\}$ such that $X_i$ is the set of ends of a fake edge of $C^-$ . Let s be the smallest index in $\mathcal I$ , and let e be the corresponding fake edge. Since $H_k, \dots, H_j$ is a reduction sequence, there is a collection $\mathcal F_s$ of s independent flaps of $H_s$ such that $(A_s, B_s) \in \mathcal F_s$ and $\sum_{(A',B') \in \mathcal F_s}|V(A')| +|E(A')|$ is minimum. Let (A,B) be an arbitrary flap in $\mathcal F_s \setminus \{(A_s, B_s)\}$ .

There are several cases to consider depending on how A and C interact.

Suppose that V(A) is a proper subset of V(C). Since $C^+$ is 3-connected and $V(C) \setminus V(A) \neq \emptyset$ , for some $Y \in \{X_s, X\}$ , one vertex y of Y is in $V(A) \setminus V(B)$ and the other vertex of Y is in $V(B) \setminus V(A)$ . Observe that $V(A_s) \subseteq V(B)$ because $(A_s, B_s)$ and (A,B) are independent flaps of $H_s$ . In particular, $X_s \subseteq V(B)$ . By the minimality of $\sum_{(A',B') \in \mathcal F_s}|V(A')| +|E(A')|$ , if $H_s$ contains an edge f whose ends are X, then $f \in E(B)$ . Since V(A) is a proper subset of V(C) and each $x \in X$ is incident to an edge of D, this implies $X \subseteq V(B)$ . Therefore, for either choice of Y, we have $y \in V(B)$ . Thus, $y \in V(A \cap B)$ , which contradicts that $y \in V(A) \setminus V(B)$ .

Suppose that $V(A)=V(C)$ and $|X_s \cup X| \geqslant 3$ . Observe that $X_s \cup X \subseteq V(A)$ . Since $V(A_s) \subseteq V(B)$ , $X_s \subseteq V(B)$ . Moreover, since $V(D) \subseteq V(B)$ , $X \subseteq V(B)$ . Therefore, $X_s \cup X \subseteq V(A \cap B)$ . Since $|X_s \cup X| \geqslant 3$ , this implies that (A,B) is a $(\geqslant 3)$ -separation of $H_s$ , which contradicts that (A,B) is a flap.

Suppose that $A \cap C=S$ , where S is a stable set and S contains a vertex $x \notin X$ . If $x \notin X_s$ , then x is an isolated vertex of A. If $x \in X_s$ , then since (A,B) and $(A_s, B_s)$ are independent flaps, $V(A \cap A_s) \setminus X_s = \emptyset$ . Thus, x is an isolated vertex of A in this case as well. But now, replacing (A,B) by $(A-x, B)$ contradicts the minimality of $\sum_{(A',B') \in \mathcal F_s}|V(A')| + |E(A')|$ .

Suppose that $A \cap C$ consists of just a single edge xy. Since $C^+$ is 3-connected, $\deg_{C^+}(x) \geqslant 3$ and $\deg_{C^+}(y) \geqslant 3$ . For $ z \in \{x,y\}$ , let d(z) be the number of $Y \in \{X_s, X\} \setminus \{\{x,y\}\}$ such that $z \in Y$ . Observe that $\deg_{C^+}(z) \leqslant \deg_{A \cap C}(z) + \deg_{B \cap C} (z)+d(z)$ for both $z \in \{x,y\}$ . Since $\deg_{A \cap C}(z)=1$ for both $z \in \{x,y\}$ , this yields $\deg_{B \cap C}(z) \geqslant 2-d(z)$ for both $z \in \{x,y\}$ . If $\{x,y\} \subseteq X \cup X_s$ , then $d(x) \leqslant 1 $ and $d(y) \leqslant 1$ . Therefore, $\deg_{B \cap C}(x) \geqslant 1$ and $\deg_{B \cap C}(y) \geqslant 1$ , which implies $\{x,y\} \subseteq V(A \cap B)$ . But now, $(A -xy, B \cup \{xy\})$ is a $(\leqslant 2)$ -separation, which contradicts the minimality of $\sum_{(A',B') \in \mathcal F_s}|V(A')| + |E(A')|$ . By symmetry, we may assume $y \notin X_s \cup X$ . Thus, $d(y)=0$ , which gives $\deg_{B \cap C} (y) \geqslant 2$ . In particular, $y \in V(A \cap B)$ . Moreover, since $y \notin X_s \cup X$ , we have $y\in V(C) \setminus V(D)$ , and thus $\deg_A(y)=\deg_{A \cap C}(y)=1$ . Observe that $|V(A - y) \cap V(B \cup \{xy\})| \leqslant 2$ because $V(A - y) \cap V(B \cup \{xy\}) \subseteq (V(A \cap B) \setminus \{y\}) \cup \{x\}$ . Therefore, $(A -y, B \cup \{xy\})$ is a $(\leqslant 2)$ -separation. But now $A-y$ is a half-flap contained in A, which contradicts the minimality of $\sum_{(A',B') \in \mathcal F_s}|V(A')| + |E(A')|$ .

Suppose that V(C) is a proper subset of V(A). Clearly, $X_s \subseteq V(A)$ . Also, $X_s \subseteq V(B)$ since (A,B) and $(A_s, B_s)$ are independent flaps. Therefore, $V(A \cap B)=X_s$ , since $|X_s|=2$ . Moreover, $A \cap D$ contains at least one vertex not in X, since V(C) is a proper subset of V(A). If $A \cap D$ meets $B \cap D$ at a vertex $x \notin X$ , then $x \notin X_s$ and $x \in V(A \cap B)$ , which contradicts that $V(A \cap B)=X_s$ . Thus, $V(A \cap D) \cap V(B \cap D) \subseteq X$ . It follows that $A \cap D$ is a half-flap, since $|X| \leqslant 2$ . However, this contradicts the minimality of $\sum_{(A',B') \in \mathcal F_s}|V(A')| +|E(A')|$ since $|V(A \cap D)| < |V(A)|$ .

Suppose that $3 \leqslant |V(A \cap C)| < |V(C)|$ and $V(A) \setminus V(C) \neq \emptyset$ . Since $C^+$ is 3-connected, for some $Y \in \{X_s, X\}$ , one vertex y of Y is in $V(A) \setminus V(B)$ and the other vertex of Y is in $V(B) \setminus V(A)$ . Since (A,B) and $(A_s, B_s)$ are independent flaps, we have $A_s \subseteq B$ . Thus, $X_s \subseteq V(B)$ , and so $Y=X$ . Let $B^*$ be obtained from B by replacing $A_s$ by an edge whose ends are $X_s$ , and adding the edge with ends X. Since $C^+$ is 3-connected, $(C^+ \cap A, C^+ \cap B^*)$ is a $(\geqslant 3)$ -separation of $C^+$ . It follows that $A \cap C$ meets $B \cap C$ in at least two vertices of $V(C) \setminus X$ and thus exactly two since $|V(A \cap B)| \leqslant 2$ . In particular, $V(A \cap B) \subseteq V(C) \setminus X$ , and hence $V(A \cap D) \cap V(B \cap D) = \emptyset$ . It follows that $A \cap D$ is a half-flap. However, this contradicts the minimality of $\sum_{(A',B') \in \mathcal F_s}|V(A')| +|E(A')|$ since $|V(A \cap D)| < |V(A)|$ .

By the previous cases, there are only two cases left to consider for (A, B), namely (1) $V(A \cap C)\subseteq X$ and $A \cap C$ has no edges, or (2) $V(A)=V(C)$ and $|X_s \cup X| \leqslant 2$ . Since (A,B) is an arbitrary flap of $\mathcal F_s \setminus \{(A_s, B_s)\}$ , we may assume that either $V(A' \cap C)\subseteq X$ and $A' \cap C$ has no edges for all $(A',B') \in \mathcal F_s \setminus \{(A_s, B_s)\}$ ; or that $V(A)=V(C)$ and $|X_s \cup X| \leqslant 2$ .

Suppose that $V(A' \cap C)\subseteq X$ and $A' \cap C$ has no edges for all $(A',B') \in \mathcal F_s \setminus \{(A_s, B_s)\}$ . By replacing $(A_s, B_s)$ by $(A_s +_{X_s} C, B_s -(V(C) \setminus X))$ in $\mathcal F_s$ , we contradict that $A_s$ is a full-half-flap.

The last case is that $V(A)=V(C)$ and $|X_s \cup X| \leqslant 2$ . Since $X_s$ is the set of ends of a fake edge of $C^-$ ; this implies that $X_s \neq X$ . Thus, we must have $|X|=1$ and $X \subseteq X_s$ . Let t be the smallest index in $\mathcal I$ larger than s, and let f be the corresponding fake edge. Note that t exists since $C^-$ contains a fake edge with neither end in X. Let $\mathcal F_t$ be a collection of t independent flaps of $H_t$ such that $(A_t, B_t) \in \mathcal F_t$ and $\sum_{(A',B') \in \mathcal F_t}|V(A')|+|E(A')|$ is minimum. Let $(A^*,B^*)$ be an arbitrary flap in $\mathcal F_t \setminus \{(A_t, B_t)\}$ . Let $A_s^* \subseteq H_t$ be obtained from $A_s$ by reversing all the flap reductions for all $j \in [s,t]$ . The reTheorem 1.2der of the proof is essentially the same as the previous cases with $(A^*,B^*)$ taking the role of (A,B) and $\{X_s, X_t\}$ taking the role of $\{X_s, X\}$ . For completeness, we include all the details.

Suppose that $V(A^*)$ is a proper subset of V(C). Since C is 3-connected, for some $Y \in \{X_s, X_t\}$ , $V(A^*) \setminus V(B^*)$ contains one vertex y of Y and $V(B^*) \setminus V(A^*)$ contains the other vertex of Y. By Lemma 5.8, $A_s^*$ and $A_t$ are both connected. Since $V(A^*) \subseteq V(C)$ , this implies $X_s \cup X_t \subseteq V(B^*)$ . Thus, for either choice of Y, we have $y \in V(A^* \cap B^*)$ , which contradicts that $y \in V(A^*) \setminus V(B^*)$ .

Suppose that $V(A^*)=V(C)$ . Clearly, $X_s \cup X_t \subseteq V(C)=V(A^*)$ . Since $A_s^*$ and $A_t$ are both connected by Lemma 5.8, $X_s \cup X_t \subseteq V(B^*)$ . Therefore, $X_s \cup X_t \subseteq V(A^* \cap B^*)$ . Since $|X_s \cup X_t| \geqslant 3$ , this implies that $(A^*,B^*)$ is a $(\geqslant 3)$ -separation of $H_t$ , which contradicts that $(A^*,B^*)$ is a flap.

Suppose that $A^* \cap C=S$ , where S is a stable set and S contains a vertex $x \notin X_s$ . If $x \notin X_t$ , then x is an isolated vertex of A. If $x \in X_t$ , then since $(A^*,B^*)$ and $(A_t, B_t)$ are independent flaps, $V(A^* \cap A_t) \setminus X_t = \emptyset$ . Thus, x is an isolated vertex of $A^*$ in this case as well. But now, replacing $(A^*,B^*)$ by $(A^*-x, B^*)$ contradicts the minimality of $\sum_{(A',B') \in \mathcal F_t}|V(A')| + |E(A')|$ .

Suppose that $A^* \cap C$ consists of just a single edge xy. Since C is 3-connected, $\deg_{C}(x) \geqslant 3$ and $\deg_{C}(y) \geqslant 3$ . For $ z \in \{x,y\}$ , let d(z) be the number of $Y \in \{X_s, X_t\} \setminus \{\{x,y\}\}$ such that $z \in Y$ . Observe that $\deg_{C}(z) \leqslant \deg_{A^* \cap C}(z) + \deg_{B^* \cap C} (z)+d(z)$ for both $z \in \{x,y\}$ . Since $\deg_{A^* \cap C}(z)=1$ for both $z \in \{x,y\}$ , this yields $\deg_{B^* \cap C}(z) \geqslant 2-d(z)$ for both $z \in \{x,y\}$ . If $\{x,y\} \subseteq X_s \cup X_t$ , then $d(x) \leqslant 1 $ and $d(y) \leqslant 1$ . Therefore, $\deg_{B^* \cap C}(x) \geqslant 1$ and $\deg_{B^* \cap C}(y) \geqslant 1$ , which implies $\{x,y\} \subseteq V(A^* \cap B^*)$ . But now, $(A^* -xy, B^* \cup \{xy\})$ is a $(\leqslant 2)$ -separation, which contradicts the minimality of $\sum_{(A',B') \in \mathcal F_t}|V(A')| + |E(A')|$ . By symmetry, we may assume $y \notin X_s \cup X_t$ . Thus, $d(y)=0$ , which gives $\deg_{B^* \cap C} (y) \geqslant 2$ . In particular, $y \in V(A^* \cap B^*)$ . Moreover, since $y \notin X_s \cup X_t$ , we have $y\in V(C) \setminus V(D)$ , and thus $\deg_{A^*}(y)=\deg_{A^* \cap C}(y)=1$ . Observe that $|V(A^* - y) \cap V(B^* \cup \{xy\})| \leqslant 2$ because $V(A^* - y) \cap V(B^* \cup \{xy\}) \subseteq (V(A^* \cap B^*) \setminus \{y\}) \cup \{x\}$ . Therefore, $(A^* -y, B^* \cup \{xy\})$ is a $(\leqslant 2)$ -separation. But now $A^*-y$ is a half-flap contained in $A^*$ , which contradicts the minimality of $\sum_{(A',B') \in \mathcal F_t}|V(A')| + |E(A')|$ .

Suppose that V(C) is a proper subset of $V(A^*)$ . Clearly, $X_t \subseteq V(A^*)$ . Also, $X_t \subseteq V(B^*)$ since $(A^*,B^*)$ and $(A_t, B_t)$ are independent flaps. Therefore, $V(A^* \cap B^*)=X_t$ , since $|X_t|=2$ . Moreover, $A^* \cap (D \cup A_s^*)$ contains at least one vertex not in $X_t$ , since V(C) is a proper subset of $V(A^*)$ . If $A^* \cap (D \cup A_s^*)$ meets $B^* \cap (D \cup A_s^*)$ at a vertex $x \notin X_s$ , then $x \in V(A \cap B)$ , which contradicts that $V(A \cap B)=X_s$ . Thus, $V(A^* \cap (D \cup A_s^*)) \cap V(B^* \cap (D \cup A_s^*)) \subseteq X_s$ . It follows that $A^* \cap (D \cup A_s^*)$ is a half-flap, since $|X_s| \leqslant 2$ . However, this contradicts the minimality of $\sum_{(A',B') \in \mathcal F_t}|V(A')| +|E(A')|$ since $|V(A^* \cap (D \cup A_s^*))| < |V(A)|$ .

Suppose that $3 \leqslant |V(A^* \cap C)| < |V(C)|$ and $V(A^*) \setminus V(C) \neq \emptyset$ . Since C is 3-connected, for some $Y \in \{X_s, X_t\}$ , one vertex y of Y is in $V(A^*) \setminus V(B^*)$ and the other vertex of Y is in $V(B^*) \setminus V(A^*)$ . Since $(A^*,B^*)$ and $(A_t, B_t)$ are independent flaps, we have $A_t \subseteq B^*$ . Thus, $X_t \subseteq V(B^*)$ , and so $Y=X_s$ . Let $\beta$ be obtained from $B^*$ by replacing $A_t$ by an edge whose ends are $X_t$ and adding the edge with ends $X_s$ . Since C is 3-connected, $(C \cap A^*, C \cap \beta)$ is a $(\geqslant 3)$ -separation of C. It follows that $A \cap C$ meets $B \cap C$ in at least two vertices of $V(C) \setminus X$ , and thus exactly two since $|V(A \cap B)| \leqslant 2$ .

Thus, $A^* \cap C$ meets $B^* \cap C$ in at least two vertices of $V(C) \setminus X_s$ , and thus exactly two since $|V(A^* \cap B^*)| \leqslant 2$ . In particular, $V(A^* \cap B^*) \subseteq V(C) \setminus X_s$ , and hence $V(A^* \cap (D \cup A_s^*)) \cap V(B^* \cap (D \cup A_s^*)) = \emptyset$ . It follows that $A \cap (D \cup A_s^*)$ is a half-flap. However, this contradicts the minimality of $\sum_{(A',B') \in \mathcal F_s}|V(A')| +|E(A')|$ since $|V(A \cap D)| < |V(A)|$ .

Since $(A^*,B^*)$ is an arbitrary flap of $\mathcal F_t \setminus \{(A_t, B_t)\}$ , by the previous cases, we may assume $V(A' \cap C)\subseteq X_s$ and $A' \cap C$ has no edges for all $(A',B') \in \mathcal F_t \setminus \{(A_t, B_t)\}$ . Therefore, by replacing $(A_t, B_t)$ by $(A_t +_{X_t} C, B_t -(V(C) \setminus X_t))$ in $\mathcal F_t$ , we contradict that $A_t$ is a full-half-flap.

We will need to pick reduction sequences that satisfy a few additional properties. Let $H_k, \dots, H_j$ be a reduction sequence of H, with corresponding flaps $(A_\ell, B_\ell)$ in $H_\ell$ . We say that $H_k, \dots, H_j$ is a good reduction sequence if for all $\ell \in \{k, \dots, j\}$ , $H_\ell$ is not a cycle, and for all $\ell \in \{k, \dots, j+1\}$

1. 1. if $A_\ell \cong P_3$ and $V(A_\ell) \cap V(B_\ell)=\{x\}$ , then e is a true edge of $H_\ell$ , where e is the unique edge of $A_\ell$ not incident to x,

2. 2. if $A_\ell \cong C_3$ and $V(A_\ell) \cap V(B_\ell)=\{x\}$ , then e is a true edge of $H_\ell$ , where e is the unique edge of $A_\ell$ not incident to x,

3. 3. if $A_\ell \cong C_4$ and $V(A_\ell) \cap V(B_\ell)=\{x,y\}$ , then e is a true edge of $H_\ell$ , where e is the unique edge of $A_\ell$ not incident to either x or y.

Note that, by Lemma 5.8, if $A_\ell \cong P_3$ and $V(A_\ell) \cap V(B_\ell)=\{x\}$ then x cannot be the centre of the $P_3$ , hence edge e is well-defined in case (1) above. Similarly, if $A_\ell \cong C_4$ and $V(A_\ell) \cap V(B_\ell)=\{x,y\}$ , then x and y cannot be opposite vertices of the $C_4$ , and thus e is also well-defined in case (3).

We now give conditions under which a good reduction sequence can be extended to a longer good reduction sequence. Let H’ be a graph where some edges are fake, and let $u, v \in V(H')$ . A u-culdesac of H’ is a cycle C of H’ such that $u \in V(C), \deg_{H'}(u) \geqslant 3$ , and $\deg_{H'}(w)=2$ for all $w \in V(C) \setminus \{u\}$ . A u-alley of H’ is a path P of H’ such that u is an end of P, $|V(P)| \geqslant 2, \deg_{H'}(u) \geqslant 3$ , and $\deg_P(w)=\deg_{H'}(w)$ for all $w \in V(P) \setminus \{u\}$ . A uv-path P in H’ is a uv-alley if $|V(P)| \geqslant 3$ and $\deg_{H'}(u) \geqslant 3$ and $\deg_{H'}(v) \geqslant 3$ and $\deg_{H'}(w)=2$ for all $w \in V(P) \setminus \{u,v\}$ .

Proof. Let $\mathcal F$ be a collection of f(H’) independent flaps in H’, and let $\mathcal F'$ be the collection of flaps $(F_1, F_1') \in \mathcal F$ such that $E(F_1 \cap C) \neq \emptyset$ . Since C contains a set of $m\;:\!=\;\lfloor \frac{|V(C)|}{2} \rfloor$ independent half-flaps of H’, we must have $|\mathcal F'| \geqslant m$ ; otherwise, $|\mathcal F|$ is not maximum. If $\mathcal F'$ contains a flap $(F_1, F_1')$ such that $F_1 \cap C=uv$ , then we replace $(F_1, F_1')$ by $(F_1 - v, F_1' \cup \{uv\})$ . Similarly, we may assume that $\mathcal F'$ does not contain a flap $(F_1, F_1')$ such that $F_1 \cap C=tu$ , where t is the other neighbour of u in C. In particular, $|E(F_1 \cap C)| \geqslant 2$ for all $(F_1, F_1') \in \mathcal F'$ . This implies that $|\mathcal F'| \leqslant m$ , and hence $|\mathcal F'|=m$ . Observe that C contains a set $\mathcal H$ of m independent half-flaps with $P \in \mathcal H$ if $|V(C)|$ is even, and $Q \in \mathcal H$ if $|V(C)|$ is odd. It follows that P can be extended to a full-half-flap P’ if $|V(C)|$ is even, and Q can be extended to a full-half-flap Q’ if $|V(C)|$ is odd. Since every collection of f(H’) independent flaps of H’ must contain at least m flaps that use an edge of C, and $\bigcup_{F \in \mathcal H} F=C$ , it follows that $C \cap P'=P$ . If P’ is not contained in C, then P’ contains two independent half-flaps, which is a contradiction. Thus, $P'=P$ . The same argument gives $Q'=Q$ .

The same proof also establishes the following claim for uv-alleys.

An edge e is at distance 2 from a vertex u if e is not incident to u and e is incident to an edge that is incident to u. A u-culdesac C is tame if C has a true edge at distance 2 from u. A uv-alley P is tame if P has a true edge at distance 2 from u or v. A u-alley P is tame if P has a true edge at distance 2 from u. Finally, we say that H’ is tame if for all $u,v \in V(H')$ all u-culdesacs, u-alleys, and uv-alleys of H’ are tame.

Proof. Suppose that $H_j$ contains a u-culdesac C with $|V(C)| \geqslant 4$ . Since $H_j$ is tame, C contains a true edge e at distance 2 from u. If $|V(C)|$ is even (respectively, odd), let P be the 3-vertex (respectively, 4-vertex) path of C such that one end of P is u and $e \notin E(P)$ . By Claim 5.12, P is a full-half-flap of $H_j$ . Letting $H_{j-1}$ be obtained from $H_j$ by applying Lemma 5.8 with $A=P$ , we have that $H_\ell, \dots, H_{j-1}$ is a good reduction sequence and $H_{j-1}$ is tame. Thus, we may assume that all culdesacs of $H_j$ are triangles. By Claim 5.13, we may also assume that for all $u,v \in V(H_j)$ , all uv-alleys of $H_j$ have at most four vertices.

Let $(A_j, B_j)$ be a flap of $H_j$ such that $A_j$ is a full-half-flap and let $H_{j-1}=B_j^+$ . Suppose $H_{j-1}$ is a cycle. If $(A_j, B_j)$ is a 1-separation, then $H_{j-1} \cong C_3$ , since all culdesacs of $H_j$ are triangles. Since $f(C_3)=1$ , this contradicts $j \geqslant 3$ . If $(A_j, B_j)$ is a 2-separation, then $H_{j-1} \in \{C_3, C_4\}$ since all alleys of $H_j$ have at most four vertices. In either case, $f(H_j)=2$ , which contradicts $j \geqslant 3$ . Thus, $H_{j-1}$ is not a cycle.

Since $H_j$ is tame, it follows that $H_k, \dots, H_{j-1}$ is a good reduction sequence. It only reTheorem 1.2s to show that $H_{j-1}$ is tame. Towards a contradiction, suppose $H_{j-1}$ contains a u-culdesac C that is not tame. The cases in which $H_{j-1}$ contains a u-alley that is not tame, or a uv-alley that is not tame are similar and are omitted. We assume that $(A_j,B_j)$ is a 2-separation (the case that $(A_j,B_j)$ is a 1-separation is easier and is omitted). Since $H_j$ is tame, there must be an edge $xy \in E(C)$ such that $V(A_j) \cap V(B_j)=\{x,y\}$ . Let $P_{xu}$ and $P_{yu}$ be the x–u and y–u paths in C such that $V(P_{xu}) \cap V(P_{yu})=\{u\}$ . Since all alleys of $H_j$ have at most four vertices, $|V(P_{xu})|, |V(P_{yu})| \leqslant 4$ . Moreover, if $|V(P_{xu})| \in \{2, 4\}$ , then adding the edge of $P_{xu}$ incident to x to $A_j$ contradicts that $A_j$ is a full-half-flap. Thus, $|V(P_{xu})|, |V(P_{yu})| \in \{1, 3\}$ . In particular, this implies that C is not a triangle. For each fake edge $e \in E(C)$ let $\ell(e)$ be the smallest index such that $V(A_{\ell(e)}) \cap V(B_{\ell(e)})$ is equal to the set of ends of e. Among all fake edges of $C \setminus \{xy\}$ in $H_{j-1}$ , let f be such that $\ell(f)$ is smallest. Since C is not a triangle, there are two edges of C at distance 2 from u (both of which are fake). Therefore, f exists. Let g be the unique edge of C such that $f \cup g$ is $P_{xu}$ or $P_{yu}$ . Then adding g to $A_{\ell(f)}$ contradicts that $A_{\ell(f)}$ is a full-half flap.

In the case that H is non-planar, we do not need $j \geqslant 3$ in the statement of Claim 5.14.

Proof. The proof is identical to the proof of Claim 5.14, except for the second paragraph. Instead of using the assumption $j \geqslant 3$ , we directly observe that $H_{j-1}$ cannot be a cycle because $H_{j-1}$ is non-planar. Note that if $j=1$ , then $H_1$ contains a flap since it is non-planar. Therefore, $H_0$ exists.

The final ingredient we need is the existence of a certain collection of paths in H. Let $H_k, \dots, H_j$ be a reduction sequence of H with corresponding flaps $(A_\ell, B_\ell)$ in $H_\ell$ , and for each $\ell \in \{k, \dots, j\}$ let $F_\ell$ be the set of fake edges of $H_\ell$ . For each fake edge e, we define a set of indices $\mathcal I(e)$ recursively as follows. Let $\ell$ be the largest index such that e is a fake edge of $H_\ell$ and recursively define $\mathcal I(e)=\{\ell+1\} \cup \bigcup_{f \in F_{\ell+1} \cap E(A_{\ell+1})}\mathcal I(f)$ .

Proof. We proceed by reverse induction. Since $H_k=H$ does not contain any fake edges, we may take $\mathcal P_k\;:\!=\;\emptyset$ . Suppose the claim is true for some $\ell > j$ , and consider $\ell-1$ . If $|V(A_\ell) \cap V(B_\ell)|=2$ then let $\{a,b\}\;:\!=\;V(A_\ell) \cap V(B_\ell)$ . We are done by induction if $|V(A_\ell) \cap V(B_\ell)| \leqslant 1$ or $e\;:\!=\;ab$ is a true edge of $H_{\ell-1}$ . Thus, we may assume that e is a fake edge of $H_{\ell-1}$ . By the final part of Lemma 5.8, there is path $P_{e}'$ in $A_{\ell}$ between a and b. By induction, for each fake edge f in $P_{e}'$ , there is a path $P_f' \subseteq \bigcup_{i \in \mathcal I(f)} A_i$ . Moreover, note that if $f_1$ and $f_2$ are distinct fake edges of $H_{\ell-1}$ , then $\mathcal{I}(f_1) \cap \mathcal I (f_2)=\emptyset$ . Therefore, replacing each fake edge f of $P_{e}'$ with $P_f'$ , we obtain a path $P_{e}$ contained in $\bigcup_{i \in \mathcal I(e)} A_i$ . Every other fake edge e’ of $H_{\ell-1}$ is a fake edge of $H_{\ell'}$ for some $\ell'> \ell$ . By induction, for each such fake edge e’, there is a path $P_{e'}$ contained in $\bigcup_{i \in \mathcal I(e')} A_i$ . Note that $P_{f_1}$ and $P_{f_2}$ are internally disjoint for all distinct $f_1, f_2 \in F_{\ell-1}$ , since $\mathcal{I}(f_1) \cap \mathcal I (f_2)=\emptyset$ Thus, $\mathcal P_{\ell-1}\;:\!=\;\{P_{f} \mid f \in F_{\ell-1}\}$ is the required set of paths.

We now prove the theorem in the case that H is non-planar.

Before proceeding with the proof, we quickly show that Claim 5.17 does indeed imply Theorem 5.9 when H is non-planar. First note that $H_k, \dots, H_0$ exist by Claim 5.15. Next, applying Claim 5.17 for $\ell=k$ , we get that there are at most $c_{4.1}(h,g)c_{5.1}(h, g+2)^k \cdot n^k \leqslant c_{5.9}(h,g)n^k$ images of H in G.

Proof. We proceed by induction on $\ell$ . When $\ell=0$ , there are at most $c_{4.1}(h,g)$ images of $H_0 \setminus F_0$ in G that extend to an image of H in G, by Theorem 4.1. For the inductive step, suppose there are at most $c_{4.1}(h,g)c_{5.1}(h, g+2)^\ell \cdot n^\ell$ images of $H_\ell \setminus F_\ell$ in G that extend to an image of H in G, and consider $\ell+1$ .

Let $\phi\;:\;V(H_\ell \setminus F_\ell) \to V(G)$ be a fixed copy of $H_\ell \setminus F_\ell$ in G that extends to an image $\psi\;:\;V(H) \to V(G)$ of H in G. For every subgraph S of H, let $S^\psi$ be the subgraph of G obtained by restricting $\psi$ to S. Let $(A_{\ell+1}, B_{\ell+1})$ be the flap in $H_{\ell+1}$ such that $H_\ell=B_{\ell+1}^+$ , and let $F_{A_{\ell+1}}$ be the set of fake edges of $H_{\ell+1}$ contained in $E(A_{\ell+1})$ . By Claim 5.16, there is a collection of paths $\mathcal P^\psi\;:\!=\;\{P_f^\psi \mid f \in F_{A_{\ell+1}}\}$ in $H^\psi$ such that for all $f \in F_{A_{\ell+1}}$ , $P_f^\psi$ has the same ends as $f^\psi$ and $((A_{\ell+1} \setminus F_{A_{\ell+1}})^\psi \cup \mathcal{P}^\psi, \mathcal {P}^\psi)$ is a partially subdivided subgraph of $H^\psi$ .