2.1. Connected antimatchings

Fundamental to our proofs is the concept of a connected antimatching: this is a set $M$ of disjoint edges in an oriented graph $D$ such that every pair of edges in $M$ is connected by an antidirected walk in $D$ (see Definition 4.5). Section 4 is dedicated to connected antimatchings. First, we will prove that any oriented graph of large minimum semidegree contains a large connected antimatching $M$ . Second, we will show that we can choose such an antimatching $M$ in a way that the edges of $M$ lie at bounded distance $d$ from each other.

2.2. Sketch of the proof of Theorem 1.4

Given an oriented graph $D$ and an antidirected tree $T$ fulfilling the conditions of the theorem, we apply the digraph regularity lemma to $D$ to find a partition into a bounded number of clusters. The reduced oriented graph $R$ maintains the condition on the minimum semidegree and thus has a large connected antimatching whose edges lie at bounded distance from each other. (In particular, the clusters covered by $M$ can accommodate all of $T$ .)

Now we turn to our antidirected tree $T$ . We decompose $T$ into a family $\mathcal{T}$ of small subtrees (for details see Section 3.2). As we prove in Section 3.3, it is possible to assign the trees in $\mathcal{T}$ to edges of $M$ in a way that they will fit comfortably into the corresponding clusters.

Figure 1. Regularise $D$ to obtain $R$ , with a connected antimatching marked in bold.

Figure 2. Embedding a small antidirected tree $S$ in $D$ .

We now embed $T$ as follows. We go through the decomposition of $T$ , embedding one small tree at a time, always keeping the embedded part connected in (the underlying tree of) $T$ . We embed the first $d$ levels of each small tree $S$ into the clusters of an antiwalk in the reduced oriented graph that starts at the already embedded parent of the root of $S$ and leads to the edge $CD$ of $M$ that was assigned to $S$ . All later levels of $S$ are embedded into clusters $C$ and $D$ . Since $T$ has bounded maximum degree, the union of first $d$ levels of the trees in $\mathcal{T}$ is very small, and therefore it is not a problem if the first $d$ levels of $S$ are embedded outside the edge $CD$ . After going through all $S$ , we have finished the embedding of $T$ . See Figures1 and 2 for an illustration.

2.3. Sketch of the proof of Theorem 1.7

Let a long $k$ -antisubdivision of $K_h$ be given, together with an oriented graph $D$ satisfying the conditions of the theorem. Since the antisubdivision is long, we can choose a set $\mathcal P$ of long antidirected paths of the antisubdivision such that deleting two inner vertices of each of the antidirected paths in $\mathcal P$ leaves us with an antidirected tree $T$ .

As in the proof of Theorem 1.2, we find a connected antimatching $M$ in the reduced oriented graph of $D$ (see Section 4 for details). We embed $T$ with the help of $M$ as follows. Fixing one edge $e$ of $M$ , we embed the branch vertices of the antisubdivision into the clusters corresponding to $e$ . We embed the long antipaths into clusters corresponding to $e$ and to other edges of $M$ , with the first and last vertices on these antipaths going to clusters on antidirected paths in the reduced oriented graph that connect the edges of $M$ .

We finish the embedding by adding the two deleted vertices on the paths from $\mathcal P$ . Their neighbours were embedded into the clusters corresponding to the edge $e$ and regularity allows us to connect them by a $3$ -edge path on unused vertices. This finishes the embedding of the antisubdivision.

2.4. Sketch of the proof of Theorem 1.9

Given the antidirected tree $T$ and the oriented graph $D$ as in the theorem, we start by finding an oriented subgraph $D'$ of $D$ where each vertex has either out-degree at least $\frac k2$ or out-degree $0$ , and either in-degree at least $\frac k2$ or in-degree $0$ . Moreover, $D'$ has at least one edge.

We then transform $D'$ into an oriented graph $D''$ which has minimum semidegree exceeding $\frac k2$ . More precisely, $D''$ consists of four copies of $D'$ , two of them with all edges reversed, glued together appropriately.

We now need Theorem 5.2, a variation of Theorem 1.2 which allows us to embed $T$ into $D''$ , guaranteeing that the root of $T$ is embedded in a small set of $V(D)$ which we can choose before the embedding. We choose to have the root $v$ of $T$ embedded in a vertex $w$ of one of the original copies of $D$ (i.e. a copy with edges in the original orientation). We can further ensure that one of the edges at $v$ is embedded into an edge having the original orientation of $D$ . Then it is not hard to deduce that all of $T$ was embedded into an original copy of $D$ , and therefore, $T$ is contained in $D$ .

3.1. Basic digraph notation

A digraph is a pair of sets $(V,E)$ , where the elements of $V$ are called vertices and $E$ is a set of ordered pairs of distinct vertices in $V$ , called edges. An oriented graph is a digraph that allows at most one edge between a pair of vertices.

The edges of a digraph $D$ are directed, and we will write $uv$ for an edge that is directed from $u$ to $v$ . While a digraph may have both edges $uv,vu$ for any pair of vertices $u, v$ , an oriented graph has at most one of these edges. The out-degree $\delta ^+(v)$ of a vertex $v$ is the number of edges coming out of $v$ , and the in-degree $\delta ^-(v)$ is defined analogously. The minimum semidegree $\delta ^0(D)$ of a digraph is the minimum over the out-degrees and the in-degrees of all vertices in $D$ .

We denote by ${V_{\text{in}}}(D)$ the set of all vertices of $D$ that have no outgoing edges, while $V_{\text{out}}(D)$ is the set of all vertices of $D$ that have no incoming edges. A digraph $D$ is antidirected if $V(D)={V_{\text{in}}}(D)\cup V_{\text{out}}(D)$ . If the underlying undirected graph of $D$ is a tree, we also call $D$ an antitree. Antipaths and anticycles are defined analogously. Note that anticycles are even. The length of an antipath or anticycle is the number of edges in it.

An antiwalk (or antidirected walk) is a sequence of edges that alternate directions, but we usually denote it by writing the sequence of the corresponding vertices. Note that an antiwalk may repeat vertices and edges, and a repeated vertex $v$ may have both outgoing and incoming edges in the antiwalk. The length of an antiwalk is the length of the corresponding sequence of edges. For instance, the antiwalk $abab$ has length $3$ , while having only one edge.

Finally, an antitree $T$ is balanced if $|V_{\text{in}}(T)|=|V_{\text{out}}(T)|$ . Note that antipaths of odd length are balanced.

3.2. Tree decompositions

In our proof of the main theorem, we will have to partition the given antitree into smaller trees. It will be enough to define this decomposition for undirected trees, as we can apply it later to the underlying graph of our antitree. This type of decomposition appeared in the literature already in the 1990’s, for instance in [Reference Ajtai, Komlós and Szemerédi3]. Here we use a version from [Reference Besomi, Pavez-Signé and Stein6]:

Let us see what happens to a balanced tree $T$ if we remove some vertices from the upper levels of the trees $S\in \mathcal T$ of the tree-decomposition of $T$ . We first define what exactly we wish to remove. As usual, the $j$ th level of a tree $S$ contains every vertex in $S$ that has distance $j$ to the root of $S$ .

We show now that after removing $L_j(T)$ from $T$ for some bounded $j$ , the remainder of $T$ is still relatively well balanced.

Lemma 3.4. Let $k, j\in \mathbb{N}^+$ , $\alpha, \beta \in (0, \frac 12)$ . Let $T$ be a balanced rooted antitree with $k$ edges such that $\Delta (T)\leq (\frac{\alpha \beta k}8)^{\frac 1{j+1}}$ . Let $(W,\mathcal{T})$ be a $\beta$ -decomposition of $T$ . Then, $(1-\alpha )p_T \leq q_T \leq (1+ \alpha )p_T$ , where

\begin{equation*}p_T\;:\!=\;|V_{ {in}}(T) - L_{j}(T)| { \,\,and \,\,}q_T\;:\!=\;|V_{ {out}}(T) - L_{j}(T)|.\end{equation*}

Proof. Note that $L_j(T)$ is contained in the union of the balls of radius $j$ centred at the vertices of  $W$ . Thus

\begin{equation*}|L_j(T)|\le |W|\cdot \Delta ^{j+1}\le \frac {2\Delta ^{j+1}}\beta \le \frac {\alpha k}{4}.\end{equation*}

As $T$ is balanced, we easily deduce the desired inequalities.

3.3. Packing trees into edges

Once the given antitree is cut into small pieces $S$ , and we shaved off their first levels $L_j$ , the details of which are described in Section 3.2, we will have to decide how to pack the remainder of the small pieces into the edges of the connected antimatching of the reduced oriented graph. The following lemma shows how to allocate all of the $S\setminus L_j(T)$ .

Lemma 3.5. Let $m, t\in \mathbb{N}$ , $\alpha \gt 0$ and let $(p_i, q_i)_{i\in I}\subseteq \mathbb{N}^2$ be a family such that:

1. (a) $(1-\alpha )\sum _{i\in I} p_i \leq \sum _{i\in I} q_i \leq (1+\alpha )\sum _{i\in I} p_i$ ,

2. (b) $p_i + q_i \leq \alpha m$ , for all $i\in I$ , and

3. (c) $\max \{\sum _{i\in I} p_i, \sum _{i\in I} q_i\} \lt (1-10\alpha )mt$ .

Then there is a partition $\mathcal{J}$ of $I$ of size $t$ such that for every $J\in \mathcal{J}$ ,

\begin{equation*}\sum _{j\in J} p_j \leq (1-7\alpha )m { \ and \ } \sum _{j\in J} q_j \leq (1-7\alpha )m.\end{equation*}

Proof. For every $i\in I$ , set $\delta _i\;:\!=\;p_i-q_i$ and for every $S\subseteq I$ , define $\delta _S: = \sum _{i\in S} \delta _i$ . Let $A_1, \ldots, A_t\subseteq I$ be disjoint sets such that for every $j\in [t]$ ,

(1) \begin{equation} \text{$\sum _{i\in A_j} p_i \leq (1-9\alpha )m$ and $\delta _{A_j} \in [{-} \alpha m, \alpha m]$,} \end{equation}

and such that, under these conditions, $R\;:\!=\;I\setminus (A_1\cup \ldots \cup A_t)$ is minimised. Note that for each $j\in R$ there is an index $k(j)\in [t]$ such that

(2) \begin{equation} \text{$ p_j+\sum _{i\in A_{k_p(j)}} p_i \leq (1-9\alpha )m$,} \end{equation}

since otherwise, using the fact that $p_j\le \alpha m$ by (b), we have

\begin{equation*}\sum _{i\in I} p_i \ge \sum _{k\in [t]}\sum _{i\in A_k} p_i \gt t\cdot ((1-9\alpha )m-p_j) \ge t\cdot (1-10\alpha )m,\end{equation*}

a contradiction to (c). Next, we claim that

(3) \begin{equation} \delta _i\delta _j \geq 0 \text{ for every }i,j\in R. \end{equation}

To see (3), suppose there are $a,b\in R$ with $\delta _a\delta _b \lt 0$ . Say $p_a\geq p_b$ . Then there is an index $k(a)$ such that (2) holds with $j=a$ , and since $p_a\ge p_b$ , the inequality also holds when substituting $p_a$ with $p_b$ . Moreover, since $a\in R$ , we know that neither $a$ nor $b$ can be added to $A_{k(a)}$ without violating (1), and thus

\begin{equation*}\delta _{A_{k(a)}} + \delta _a, \delta _{A_{k(a)}} + \delta _b \notin [{-}\alpha m, \alpha m].\end{equation*}

However, $\delta _{A_{k(a)}} \in [{-}\alpha m, \alpha m]$ by (ii). So, since we assumed that $\delta _a\delta _b\lt 0$ , it must be that $|\delta _a|+|\delta _b|\gt 2\alpha m$ . But this contradicts (b). We proved (3), which enables us to split the rest of the proof into two cases.

Case 1: $\delta _i\ge 0$ for all $i\in R$ . For $k\in [t]$ , we let $A^{\prime}_k\supseteq A_k$ be disjoint sets such that $\sum _{i\in A^{\prime}_k} p_i \leq (1-9\alpha )m$ for every $k\in [t]$ , and thus also,

(4) \begin{equation} \sum _{i\in A^{\prime}_k} q_j = \sum _{i\in A^{\prime}_k} (p_j - \delta _{A^{\prime}_k}) \le \sum _{i\in A^{\prime}_k} (p_j - \delta _{A_k}) \leq (1-9\alpha )m + \alpha m \lt (1-7\alpha )m. \end{equation}

Similarly as for (2), we can show that for each $j\in R'\;:\!=\;I\setminus (A^{\prime}_1\cup \ldots \cup A^{\prime}_t)$ there is an index $k'(j)\in [t]$ with $ p_j+\sum _{i\in A^{\prime}_{k_p(j)}} p_i \leq (1-9\alpha )m$ , and thus, by (4), $q_j+\sum _{i\in A^{\prime}_{k_p(j)}} q_i \leq (1-9\alpha )m$ . So $R'=\emptyset$ , and we are done, taking $\mathcal{J}= \{A^{\prime}_1, \ldots, A^{\prime}_t\}$ .

Case 2: $\delta _i\le 0$ for all $i\in R$ . We proceed as in Case 1, but choose sets $A^{\prime}_k\supseteq A_k$ such that $\sum _{i\in A^{\prime}_k} q_i \leq (1-9\alpha )m$ for every $k\in [t]$ . The rest of the argument is similar.

3.4. Diregularity

We will use the regularity method which goes back to Szemerédi’s work from the 1970’s [Reference Szemerédi31]. We will need regularity for oriented graphs, but start introducing the concept for undirected graphs. Let $G$ be a graph, let $\varepsilon \gt 0$ and let $A,B$ be two disjoint subsets of $V(G)$ . The density of the pair $(A,B)$ is $d(A,B)=\frac{|E(A,B)|}{|A|\cdot |B|}$ , with $|E(A,B)|$ denoting the number of edges between $A$ and $B$ . The pair $(A,B)$ is $\varepsilon$ -regular if $|d(X,Y)-d(A,B)|\lt \varepsilon$ for every $X\subseteq A$ and $Y\subseteq B$ satisfying $|X|\gt \varepsilon |A|$ and $|Y|\gt \varepsilon |B|$ .

Let $(A,B)$ be an $\varepsilon$ -regular pair of density $d$ and let $Y\subseteq B$ be such that $|Y|\gt \varepsilon |B|$ . A vertex $x\in A$ is called $\varepsilon$ -typical (or simply typical) with respect to $Y$ if it has more than $(d-\varepsilon )|Y|$ neighbours in $Y$ . It is well known and easy to prove that $A$ has at most $\varepsilon |A|$ vertices that are not typical with respect to $Y$ .

A partition $\{V_0, \ldots, V_k\}$ of $V(G)$ is called an $\varepsilon$ -regular partition of $G$ if

1. (i) $|V_0|\leq \varepsilon |V|$ ,

2. (ii) $|V_1| = \ldots = |V_k|$ ,

3. (iii) all but at most $\varepsilon k^2$ of the pairs $(V_i, V_j)$ , with $1\leq i \lt j\leq k$ , are $\varepsilon$ -regular.

Let $D$ be a digraph and let $A,B\subseteq V(D)$ disjoint. We denote by $(A,B)$ the oriented subgraph of $D$ with vertex set $A\cup B$ and every edge directed from $A$ to $B$ in $D$ . In this case, we say the pair $(A,B)$ is $\varepsilon$ -regular if the underlying graph is $\varepsilon$ -regular. With these notions and based on the Szemerédi’s Regularity Lemma for graphs without orientation [Reference Szemerédi31], we show its version for digraphs as stated by Alon and Shapira in [Reference Alon and Shapira4]:

Given a regularised digraph $D'$ with clusters $V_1, \ldots, V_t$ , the reduced digraph $R$ is a digraph with vertices $V_1, \ldots, V_t$ such that the edge $V_iV_j$ exists only if $D'$ contains a $V_i$ - $V_j$ edge. Observe that, $R$ need not be an oriented graph, even if $D'$ is. However, it is possible [Reference Kelly, Kühn and Osthus21] to discard appropriate edges from the reduced digraph to find an oriented spanning subgraph $R'$ of $R$ that preserves the minimum semidegree of the original oriented graph $D$ (proportionally to the order of the reduced digraph). The new oriented graph $R'$ is called the reduced oriented graph. This result is formalised in the following lemma.

3.5. Embedding small trees in antiwalks

We now show how to embed a small tree into an antiwalk of the reduced oriented graph. This will be useful for embedding the first levels of a piece $S$ of the decomposition of our antitree $T$ into an antiwalk leading to a suitable edge $a_ib_i$ of the connected antimatching. The edge $a_ib_i$ will accommodate the rest of $S$ .

We start with a convenient definition, expressing that the orientations of the small tree $S$ and the antiwalk coincide.

Now we embed an antitree into a consistent antiwalk of a reduced digraph. A very similar result for undirected graphs was proved in [Reference Besomi, Pavez-Signé and Stein6].

6.1. Preparation

We choose our constants as in the proof of Theorem 1.2, in particular ensuring that $n_0\ge 100\varepsilon ^{-1}M_0^3$ . In addition, we set

\begin{equation*}\gamma \;:\!=\;\frac {\varepsilon }{10M_0}.\end{equation*}

We now prepare the oriented graph in the same way as for Theorem 1.2. In the reduced oriented graph of $D$ , we use Lemma 4.6 to find a connected antimatching $M=\{a_ib_i\}_{1\le i\le t}$ of convenient size $t$ . We split each cluster $C$ into two slices $C^1$ and $C^2$ , where $C^1$ only contains about a $10\sqrt \varepsilon$ portion of the vertices of $C$ .

Let a long $k$ -edge antisubdivision $H$ of $K_h$ be given, that is, a set $X=x_1,\ldots, x_h$ of vertices, and antipaths $P_{i,j}$ connecting $x_i$ with $x_j$ , for each $1\le i\lt j\le h$ . For each two-edge path $P_{i,j}$ we add the middle vertex $x_{i,j}$ to $X$ . Call the obtained set $X'$ . By assumption, $X'$ induces a forest in $K_h$ . Choose a subset of

\begin{equation*}\{P_{i,j}\; :\; 1\le i\lt j\le h \land e(P_{i,j})\ge 3\}\end{equation*}

so that together with $X'$ , they induce a tree in $K_h$ . For all other paths $P_{i,j}$ we choose a subpath $Q_{i,j}\subseteq P_{i,j}$ of length $3$ . Let $\mathcal Q$ be the set of all such paths $Q_{i,j}$ , and let $Y$ be the set of their endvertices. Note that $T=K_h-(\bigcup _{Q_{i,j}\in \mathcal Q}V(Q_{i,j})\setminus Y)$ is an antitree. We root $T$ at $x_1$ .

Let $Z$ be the set of all vertices on paths in $T$ between vertices of $X\cup Y$ that have length at most $M_0$ . Set $W=X'\cup Y\cup Z$ , and note that $W$ naturally partitions into two sets: $W_{in}=W\cap{V_{\text{in}}}(H)$ and $W_{out}=W\cap V_{\text{out}}(H)$ . Observe that there are at most $\frac{h^2}2$ paths $P_{i,j}$ of length at least $3$ , and thus

(17) \begin{equation} |W|\le 2h+h^2+M_0h^2\le 4M_0h^2. \end{equation}

Also note that each component of $T- W$ is a long path (longer than $M_0$ ). Let $\mathcal P$ be the set of all these components.

6.2. Embedding of $T$

We first give quick overview of the embedding of $T$ , the details are given further below. First, we embed the root $x_1$ into $C_{a_1}\cup C_{b_1}$ . Then at each step, we embed either a vertex from $W$ or a path from $\mathcal P$ whose parent is already embedded. All vertices of $W$ are embedded into $C_{a_1}^1\cup C_{b_1}^1$ , and the paths from $\mathcal P$ are embedded mainly into the $C^2$ -slices of clusters corresponding to edges of $M$ . For this, we use the edges of the antimatching $M$ (including $a_1b_1$ although this is not crucial) in an ordered way, and when one edge is sufficiently used, we go to the next edge of $M$ . For the connections between $C_{a_i}\cup C_{b_i}$ and $C_{a_j}\cup C_{b_j}$ we use the slices $C^1$ . At all times, vertices are embedded into typical vertices with respect to the unused part of the slice $C^2$ to be used in the next step, or with respect to the slice $C^1$ to be used in the future for children. The details of the embedding of $W$ are given in the next paragraph, and the details for the paths from $\mathcal P$ are given in the subsequent paragraph.

The vertices of $W$ are embedded into $C_{a_1}^1\cup C_{b_1}^1$ , as mentioned above. Namely, each $w\in W$ (in particular $x_1$ ) is embedded into $C_{a_1}^1$ if $w\in W_{out}$ and $w$ is embedded into $C_{b_1}^1$ if $w\in W_{in}$ . Every time we embed a vertex from $W$ into $C_{a_1}^1$ , we make sure its image is typical with respect to $C_{b_1}^1$ , and every time we embed a vertex from $W$ into $C_{b_1}^1$ , we make sure its image is typical with respect to $C_{a_1}^1$ . By (17), the set $W$ is small enough to easily fit into $C_{a_1}^1\cup C_{b_1}^1$ . It is also much smaller than a typical neighbourhood in $C_{a_1}^1$ or in $C_{b_1}^1$ , and therefore, it is not a problem if a vertex from $W$ is embedded much earlier than some of its children (as long as we ensure the children are embedded into $C^1$ -slices). For a more precise analysis, see below.

Let us now turn to the paths from $\mathcal P$ . As mentioned above, these paths are embedded mainly into the $C^2$ -slices of clusters corresponding to edges of the antimatching $M$ . However, the first vertex $s$ of such a path $S$ goes to either $C_{a_1}^1$ or $C_{b_1}^1$ (depending on the image of its parent), and we choose for the image of $s$ a vertex that is typical with respect to $C_0^1$ where $C_0$ is the first cluster on a path $P$ from $C_{a_1}$ , or from $C_{b_1}$ , to the clusters $C_{a_j}$ and $C_{b_j}$ we plan to use for $S$ . We embed the next vertices of $S$ along $P$ , always into $C^1$ -slices, always typical to the next slice until we reach $C_{a_j}\cup C_{b_j}$ (after at most $M_0$ steps). Then we switch to the slices $C_{a_j}^2$ and $C_{b_j}^2$ . Now, every vertex is embedded into a typical vertex with respect to the unused part of $C_{a_j}^2$ or of $C_{b_j}^2$ . If necessary, we move from $C_{a_j}\cup C_{b_j}$ to $C_{a_{j+1}}\cup C_{b_{j+1}}$ (using at most $M_0$ vertices which are embedded into $C^1$ -slices on a suitable path). We keep moving to subsequent $C_{a_i}\cup C_{b_i}$ ’s if necessary. When we reach the last vertices on $S$ , we start moving back to $C_{a_1}\cup C_{b_1}$ , through the $C^1$ -slices on a path of length at most $M_0$ . We reach $C_{a_1}\cup C_{b_1}$ and embed the last vertex of $S$ into a typical vertex with respect to $C_{a_1}^1$ or to $C_{b_1}^1$ . If $S$ has a child in $W$ , this child can be embedded now, or later in the process.

Let us analyse the embedding procedure to see that $T$ can indeed be embedded in this way. First, we note that the size of $M$ is sufficient, and the $C^2$ -slices are large enough so that all the paths from $\mathcal P$ can be embedded without a problem. Second, we observe that we used the $C^1$ -slices exclusively for $W$ , for the first $\le M_0$ and last $\le M_0$ vertices on a long path, and for moving from one edge $a_jb_j$ to the next edge $a_{j+1}b_{j+1}$ . So the number of vertices embedded into the $C^1$ -slices is at most $|W|+2M_0\cdot h^2+M_0\cdot t$ . Because of (17) and since $t\le M_0$ , this number is bounded from above by

\begin{equation*}6M_0h^2 + M_0^2 \le \varepsilon \frac n{8M_0}\le \frac \varepsilon 2 m.\end{equation*}

So, whenever are about to embed a vertex into a $C^1$ -slice, it is enough to know that the image of its parent was chosen typical with respect to the whole slice (as a typical neighbourhood in the slice has at least $18\varepsilon m$ vertices). We can thus embed all of $T$ .

6.3. Embedding interior vertices on paths from $\mathcal Q$

It only remains to embed the two middle vertices $q_{i,j}$ , $q^{\prime}_{i,j}$ of the paths $Q_{i,j}$ , which we do successively, in any order. Say the neighbour of $q_{i,j}$ was embedded in $v\in C^1_{a_1}$ , and the neighbour of $q^{\prime}_{i,j}$ was embedded in $v'\in C^1_{b_1}$ . We consider the neighbourhood $N_1$ of the image of $v$ in the unused part of $C^1_{b_1}$ and the neighbourhood $N_2$ of the image of $v'$ in the unused part of $C^1_{a_1}$ . Since at most $ \frac \varepsilon 2 m+h^2\le \varepsilon |C^1_{a_1}|$ vertices of $C^1_{a_1}$ and $C^1_{b_1}$ have been used so far, we know that $N_1$ and $N_2$ are sufficiently large to ensure that there is an edge $ww'$ we can use. We complete the embedding by mapping $v$ and $v'$ to $w$ and $w'$ .