Testing $H$-Freeness on Sparse Graphs, the Case of Bounded Expansion

For the sake of contradiction, assume the statement is false. Hence, for each graph $H$ of $ℍ$, it is possible to remove at most $ϵ|G|/|ℍ|$ edges from $G$ to make it $H$-free. If we do this for all graphs of $ℍ$, then we remove at most $ϵ|G|$ edges from $G$ and make it $ℍ$-free, a contradiction. $◀$

Given $G,ϵ,ℍ$, consider the algorithm iteratively testing $H$-freeness (with proximity parameter $ϵ/|ℍ|$) for each $H\in ℍ$. If the sub-tester for one of the graph $H\in ℍ$ rejects, then the algorithm rejects $G$. Otherwise, the algorithm accepts $G$. The number of queries is constant (depending only on $ϵ$ and $ℍ$, and possibly $𝒞$).

Note that if $G$ is indeed $ℍ$-free, since sub-testers are one-sided, they all accept, and therefore our algorithm accepts. Otherwise, if $G$ is $ϵ$-far from $ℍ$-freeness, by Proposition 2.6, there is exists $H\in ℍ$ such that $G$ is $ϵ/|ℍ|$-far from being $H$-free. With probability at least $2/3$ the sub-tester for $H$ rejects, and therefore our algorithm rejects with probability at least $2/3$ too. $◀$

Our tester for $H$-freeness is relatively straightforward. It is the same as that of [9], except that we provide formal details on how disconnected graphs are handled, whereas this particular case is only discussed informally in [9, Section 8]. Our tester is built on the subroutine for Random Bounded Breadth First Searches: RandomBoundedBFS described below.

Hence, RandomBoundedBFS does a breadth first search, with bounded breadth and depth, and at random. Our final algorithm $\text{Tester}(n,H,ϵ,G)$ rejects when $|H|>|G|$. Otherwise it removes its isolated vertices from $H$ and repeats the following $n$ times (where $n$ should be independent of $G$ to ensure constant query complexity):

1. 1.

   for every connected component $C$ of $H$, make a call to $\text{RandomBoundedBFS}(G,|H|,\mathrm{\Delta }(H))$;

2. 2.

   if the union of the subgraphs returned by the calls to RandomBoundedBFS contain a copy of $H$, then reject. If at the end of the $n$ iterations the algorithm has not rejected $G$, then accept.

Observe that a call to RandomBoundedBFS associated to a connected component $C$ of $H$ does not need to find a copy of $H$ in the algorithm. Having one call per component ensures high probability. Concerning isolated vertices of $H$, once a copy of the non-isolated parts of $H$ is found, any other vertex of $G$ can be used as a copy of an isolated vertex of $H$. And since we have $|G|\ge |H|$ there are such vertices.

We prove, given a set $\mathscr{H}$ of edge-disjoint copies of $H$ in $G$, that we can build a set of $k+1$ edge-disjoint copies of $H$ in $G$.

Removing all edges of $G[\mathscr{H}]$ from $G$ removes edges from $G$. Since $G$ is $ϵ$-far from being $H$-free, at least one copy of $H$ remains in $G-E[G[\mathscr{H}]]$. Adding it to $\mathscr{H}$ provides a set of $k+1$ edge-disjoint copies of $H$ in $G$. $◀$

We define a condition on subgraphs of $G$ and prove that the probability of finding $H$ on a subgraph of $G$ satisfying this condition lifts to $G$, up to a constant factor. This condition relates to [9, Property (a’), defined in Lemma 47].

Again, this lemma is similar to [9, Lemma 47], the main difference being that in [9], the authors assume $G^{\prime }$ to be a spanning subgraph instead of having $|G^{\prime }|\ge c|G|$ in the definition of $c$-degree preserving subgraph.

Let $F$ be a subgraph of $G^{\prime }$ which is returned by $\text{RandomBoundedBFS}(G^{\prime },d,t)$ with probability $q$. Assume the search starts on a vertex $v$ of $G^{\prime }$.

Since $G^{\prime }$ is $c$-degree preserving, RandomBoundedBFS $(G,d,t)$ now starts on $v$ with probability $1/|G|\ge c/|G^{\prime }|$ (this is the $+1$ in $c^{d^t+1}$).

Let $uw$ be an edge of $G^{\prime }$. Assume, during runs of $\text{RandomBoundedBFS}(G^{\prime },d,t)$ and $\text{RandomBoundedBFS}(G,d,t)$ both starting on $v$, that $u$ has just been visited, and $uw$ has not been discovered yet by either runs.

Since $G^{\prime }$ is $c$-degree preserving, the neighborhood of $u$ in $G$ is larger than in $G^{\prime }$ by a factor of at most $1/c$. The probabilities that the runs of $\text{RandomBoundedBFS}(G^{\prime },d,t)$ and $\text{RandomBoundedBFS}(G,d,t)$, just after visiting $u$, discover $uw$ are, respectively:

In other words, the probability that the run of $\text{RandomBoundedBFS}(G,d,t)$ discovers $uw$ just after visiting $u$ is at least $c$ times the probability that the run of $\text{RandomBoundedBFS}(G^{\prime },d,t)$ discovers $uw$ just after visiting $u$.

By construction, there are at most $d^t$ edges in $F$: the probability that RandomBoundedBFS $(G,d,t)$ discovers precisely the edges of $F$, and in the same order than RandomBoundedBFS $(G^{\prime },d,t)$ does, is at least $c^{d^t}q$.

Combining this with the probability that $\text{RandomBoundedBFS}(G,d,t)$ starts on $v$, the probability that $\text{RandomBoundedBFS}(G,d,t)$ finds a copy of $F$ in $G$ is at least $c^{d^t+1}q$. $◀$

Finally we prove that degenerate graphs containing a set $\mathscr{H}$ of many edge-disjoint copies of $H$ also contain a “significantly large” set ${\mathscr{H}}^{\prime }\subseteq \mathscr{H}$ such that $G[{\mathscr{H}}^{\prime }]$ is $c$-degree preserving.

This lemma generalizes [9, Lemma 18] to graphs with bounded degeneracy. The assumption that $|E(H)|\ge 1$ (at the end of the proof) is not a limitation with regard to our tester, since Tester treats isolated vertices separately from the rest of $H$.

We prove this statement by providing a simple algorithm computing such a set ${\mathscr{H}}^{\prime }$: take ${\mathscr{H}}^{\prime }=\mathscr{H}$ at first. While there exists a vertex of $G[{\mathscr{H}}^{\prime }]$ which is not $(\alpha /4d)$-degree preserving in $G[{\mathscr{H}}^{\prime }]$, choose one, say $v$, and remove from ${\mathscr{H}}^{\prime }$ every copy of $H$ containing $v$ in their image. This procedure starts with ${\mathscr{H}}^{\prime }=\mathscr{H}$ and ends when all vertices in $G[{\mathscr{H}}^{\prime }]$ are $(\alpha /4d)$-degree preserved. It clearly terminates after a finite number of steps.

In the following, we first argue that $|{\mathscr{H}}^{\prime }|\ge \alpha |G|/2$ and then that $|G[{\mathscr{H}}^{\prime }]|\ge \alpha |G|/4d$.

Let $v$ be a vertex that is chosen by the algorithm to remove all its incident copies. Once the vertex $v$ is chosen by the algorithm, it cannot be selected again. Since the degree of $v$ at the moment of its selection is bounded by $\alpha {\mathrm{deg}}^G(v)/4d$, and as the copies in $\mathscr{H}$ are edge-disjoint, the number of copies removed in this step is at most $\alpha {\mathrm{deg}}^G(v)/4d$.

We bound the total number of copies removed during the algorithm by summing the bounds over all vertices $v$ of $G$:

Since, furthermore, $|E(G)|\le d|G|$ and $|\mathscr{H}|\ge \alpha |G|$:

Since $G[{\mathscr{H}}^{\prime }]$ is a subgraph of $G$, $G[{\mathscr{H}}^{\prime }]$ is also $d$-degenerate, and we have

since $|E(H)|\ge 1$. Therefore, ${\mathscr{H}}^{\prime }$ is indeed $(\alpha /4d)$-degree preserving. $◀$

We define $\mathscr{H}$ with Lemmas 3.1 and 3.4. By Lemma 3.3, $\text{Tester}(n,H,ϵ,G)$ finds the exact same subgraph of $G[\mathscr{H}]$ as $\text{Tester}(n,H,ϵ,G[\mathscr{H}])$ with probability

(Calls to RandomBoundedBFS being independent.) Since $\text{Tester}(n,H,ϵ,G[\mathscr{H}])$ finds $H$ with probability at least $2/3$, this implies that $\text{Tester}(n,H,ϵ,G)$ finds $H$ with probability at least $p^{\prime }=2p/3$. Note that, given a positive integer $m\ge 1$, running $m$ times $\text{Tester}(n,H,ϵ,G)$ is the same as running $\text{Tester}(nm,H,ϵ,G)$. The probability that $\text{Tester}(n,H,ϵ,G)$ fails $m$ times in a row is at most ${(1-p^{\prime })}^m$.

Take $m=\lceil 2/p^{\prime }\rceil$ and $n^{\prime }=nm$, we conclude that $\text{Tester}(n^{\prime },H,ϵ,G)$ succeeds with probability at least $1-{(1-p^{\prime })}^m=1-{(1-2/m)}^m>1-e^{-2}>2/3$. $◀$

Consider a $|H|$-treedepth coloring of $G[\mathscr{H}]$, using colors $c_1,\mathrm{\dots },c_{\mathrm{\ell }}$. By Definition 2.3, $\mathrm{\ell }$ is bounded by a function only depending on $𝒞$ and $|H|$. Let $\{C_1,\mathrm{\dots },C_{{\mathrm{\ell }}^{|H|}}\}$ be the set of all $|H|$-tuples of colors. Each copy of $H$ in $\mathscr{H}$ contains $|H|$ vertices, and therefore is colored with the colors of at least one of the $C_i$. Therefore, by the pigeonhole principle, there is a tuple of colors $C_i$ such that at least $|\mathscr{H}|/{\mathrm{\ell }}^{|H|}$ copies of $H$ in $\mathscr{H}$ are colored with the colors of $C_i$. Let ${\mathscr{H}}^{\prime }$ be the set of copies that only use the colors of $C_i$.

Notice that the graph $G[{\mathscr{H}}^{\prime }]$ is a subgraph of $G[C_i]$, that is, the subgraph induced by the vertices colored with colors from $C_i$ in the $|H|$-treedepth coloring. By definition of the $|H|$-treedepth coloring, $G[C_i]$ (and therefore $G[{\mathscr{H}}^{\prime }]$) has treedepth $|H|$. We can then conclude using $|\mathscr{H}|/{\mathrm{\ell }}^{|H|}\le |{\mathscr{H}}^{\prime }|\le |\mathscr{H}|$, so $|{\mathscr{H}}^{\prime }|={\mathrm{\Theta }}_{|H|,𝒞}(|\mathscr{H}|)$. $◀$

We can now prove the reduction from bounded expansion to bounded treedepth for the success probability of the tester.

We start with Lemma 3.1 which gives a set ${\mathscr{H}}_1$ of ${\mathrm{\Omega }}_{ϵ,H}(|G|)$ many edge-disjoint copies of $H$. We then apply Lemma 3.6 yielding a set ${\mathscr{H}}_2$ such that $G[{\mathscr{H}}_2]$ has treedepth at most $|H|$ and ${\mathscr{H}}_2={\mathrm{\Omega }}_{ϵ,H,𝒞}(|G|)$. Finally, we apply Lemma 3.4 to extract a set ${\mathscr{H}}_3$ from ${\mathscr{H}}_2$ that is $c$-degree preserving for some constant $c=O_{ϵ,H,𝒞}(1)$, and still ${\mathscr{H}}_3={\mathrm{\Omega }}_{ϵ,H,𝒞}(|G|)$.

We conclude similarly as for Corollary 3.5: thanks to Lemma 3.3. $◀$

By Lemma 3.7, it is sufficient to prove the statement when $𝒞$ is a class of graphs with bounded treedepth. This is a particular case of the main result of [9], since bounded treedepth classes are properly minor-closed. $◀$

In this proof, we have relied on [9] for graphs of bounded treedepth. However, we reprove this particular case in the next section. Hence we present a self-contained proof, that we believe to be simpler since it avoids the machinery of edge-contractions, hypergraphs and safety from [9]. Our proof also provides an insight into the structure imposed by $H$-freeness on graphs of bounded treedepth.

We believe that classes of bounded treedepth offer rich structure for property testing and thus are a suitable “simple” class in the lower ends of the sparsity hierarchy (see Figure 1). Most of the existing literature on property testing in the sparse model focuses on graphs of bounded degree or on planar graphs and does not consider classes of bounded treedepth¹¹1A notable exception is a work by Esperet and Norin [10] considering treedepth to prove 1. a linear Erdos–Posa property for monotone properties on properly minor-closed classes and 2. that proper minor-closed classes admit approximate proof labelling schemes of logarithmic complexity..

We want the inverse image of a given vertex of $G$ under all copies of ${\mathscr{H}}^{\prime }$ to be either empty or a singleton. We consider random assignements of functions $f:V(G)\to V(H)$ and look at the probability that the copies of $H$ in $\mathscr{H}$ are compatible with $f$, meaning that for every $v\in V(H)$, $f(h(v))=v$.

Write $\{h_1,\mathrm{\dots },h_N\}$ for $\mathscr{H}$ and $X_i$ for the random variable which is $1$ if $f$ is compatible with $h_i$ and $0$ otherwise. Since:

• $\mathrm{■}$

  the probability of $f(h_i(v))=v$ for a given $v$ is $1/|H|$,

• $\mathrm{■}$

  the probabilities of $f(h_i(v))=v$ are pairwise independent for distinct values of $v$, and,

• $\mathrm{■}$

  having $X_i=1$ is exactly having $f(h_i(v))=v$ for all $v\in V(H)$,

the expected value of $X_i$ is $1/{|H|}^{|H|}$. The number of copies compatible with $f$ is given by ${\sum }_i{X}_i$, and its expected value is

Therefore, there must exist some $f$ with at least this many uniformly colored copies of $H$. $◀$

Write $k$ for $|H|$ and $a_1,\mathrm{\dots },a_k$ for the vertices of $H$. Let $G$ be a graph of treedepth $d$, and $\mathscr{H}$ be a set of edge-disjoint and uniformly colored (by the vertices $a_1,\mathrm{\dots }{a}_k$) copies of $H$ in $G$. Let ${\le }_T$ be a tree embedding of $G$ with depth $d$. Let $C_1,\mathrm{\dots },C_{d^k}$ be the set of all $k$-tuples of levels. For each copy $h$ of $H$ in $\mathscr{H}$, and for each $i\le k$, there is a level ${\mathrm{\ell }}_i$ such that $h(a_i)$ lies in level ${\mathrm{\ell }}_i$ in ${\le }_T$: to $h$ we associate the tuple $C=({\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_k)$.

Since there are $d^k$ distinct tuples, there exists a $k$-tuple $C$ associated to at least $|\mathscr{H}|/d^k$ copies. Let ${\mathscr{H}}^{\prime }$ be the subset of $\mathscr{H}$ of copies associated to $C$. By construction, we have:

1. 1.

   $|{\mathscr{H}}^{\prime }|\ge |\mathscr{H}|/d^k$, and

2. 2.

   ${\mathscr{H}}^{\prime }$ is uniformly layered²²2An astute reader can notice that if ${\mathrm{\ell }}_i={\mathrm{\ell }}_j$ for some pair $i,j$ then one level can contain two or more colors. This is easily fixable by creating intermediate levels (e.g. 3.1, 3.2, $\mathrm{\dots }$) so that vertices of several colors in one level can choose arbitrarily their sub-level. E.g. if vertices blue and red are on level 3, we arbitrary put the blue vertices on level 3.1, and the red one in 3.2. This keeps at most $H$ many (sub-)levels. in ${\le }_T^{{\mathscr{H}}^{\prime }}$ (that is ${\le }_T$ restricted to the vertices of $G[{\mathscr{H}}^{\prime }]$).

$◀$

By combining this result with the lemmas from Section 3.1, testing $H$-freeness on graphs of treedepth at most $d$ is reduced to testing $H$-freeness on graphs induced by many edge-disjoint copies of $H$, of treedepth at most $|H|$, with a uniformly layered treedepth embedding of depth $|H|$. We are more precise on the combined use of these lemmas in Section 4.3.

Termination is ensured by the fact that $H$, and by extension $C_F$, contain finitely many parallel parts. At the end of a run, $ℱ$ contains precisely one copy of each part of $C_F$, including $h(F)$.

We prove soundness via the following invariant: at any step during a run of Algorithm 2, the set $ℱ$ contains pairwise compatible copies of parts of $C_F$. We then conclude with ˜4.10.

We proceed inductively over the while loop. Let $ℱ$ be given after a partial execution of the algorithm. Since the algorithm is still running, there exists a part of $C_F$ without a copy in $ℱ$. Let $h^{\prime }(F^{\prime })\in \mathscr{H}$ be a copy of a parallel part $F^{\prime }$ of $C_F$ without a copy in $ℱ$, and such that $F^{\prime }$ is adjacent to a port $s$ of $ℱ$ of maximal level in ${\le }_T$.

Assume for the sake of contradiction that $h^{\prime }(F^{\prime })$ is not compatible with some copy $h^{\prime \prime }(F^{\prime \prime })\in ℱ$: let $s^{\prime }$ be a source of $C_F$ adjacent with both $F^{\prime }$ and $F^{\prime \prime }$ but with $h^{\prime }(s^{\prime })\ne h^{\prime \prime }(s^{\prime })$.

By construction of the algorithm, the graph $G^{\prime }$ induced by the copies of parts in $ℱ\cup \{h^{\prime }(F^{\prime })\}$ as well as by the corresponding copies of adjacent sources is connected.

Consider, in $G^{\prime }$, a simple path $P$ from $h^{\prime }(s^{\prime })$ to $h^{\prime \prime }(s^{\prime })$ going through copies of parts of $H$ via the ports that led to their addition to $ℱ$. Since initially $ℱ=\{h(F)\}$, such a path is well-defined.

Let $s_m$ be the copy of a source of smallest level in ${\le }_T$ appearing on $P$. At $s_m$, $P$ must change of parallel part. It quits a copy of a part $F_1$ to enter a copy of a part $F_2$.

We perform case analysis depending on whether $F_1$ is discovered before $F_2$ by the algorithm or not.

Assume that $F_2$ is discovered after $F_1$ by the algorithm. Consider the sequence of ports that led to discoveries of parts traversed by $P$: $h^{\prime }(s^{\prime })=s_1,\mathrm{\dots },s_i,s_m,s_1^{\prime },\mathrm{\dots },s_j^{\prime }=h^{\prime \prime }(s^{\prime \prime })$.

By construction of $P$, all sources among $s_1,\mathrm{\dots },s_i$ are at a deeper level in ${\le }_T$ than $s_m$. Hence, all copies of parts of $H$ that the path $h^{\prime }(s^{\prime })=s_1,\mathrm{\dots },s_i,s_m$ traverses, as well as $h^{\prime }(F^{\prime })$, should have been discovered before the copy of $F_2$, a contradiction since $h^{\prime }(F^{\prime })$ is discovered after the copy of $F_2$.

Assume that $F_1$ is discovered after $F_2$ by the algorithm. Similarly, as in the previous case, all copies of parts of $H$ that the path $s_m,s_1^{\prime },\mathrm{\dots },s_j^{\prime }=h^{\prime \prime }(s^{\prime \prime })$ traverses, as well as a copy of $F^{\prime }$ adjacent to $h^{\prime \prime }(s^{\prime })$ should have been discovered before a copy of $F_1$, a contradiction since no copy of $F^{\prime }$ adjacent to $h^{\prime \prime }(s^{\prime })$ has been discovered. $◀$

Since $u$ is an inner vertex and ${\le }_T$ a uniformly layered treedepth embedding, the neighborhood of $h(u)$ in $G[\mathscr{H}]$ is precisely the image of $N_H(u)$ under $h$. Hence, in the step just after discovering $u$, RandomBoundedBFS finds all edges incident to $u$ with probability at least $({\mathrm{\Delta }}_H-1)!/{\mathrm{\Delta }}_H^{{\mathrm{\Delta }}_H-1}={\mathrm{\Omega }}_H(1)$. $◀$

Let $F$ and $F^{\prime }$ be two distinct parallel parts, both adjacent to a source $s$ of $H$, and let $h$ be a copy of $H$ in $\mathscr{H}$. Observe that there are as many copies of $F$ as there are of $F^{\prime }$ which are adjacent to $h(s)$ in $G$ (one each per copy with $h(s)$ in the image).

Let $N$ be the number of copies of $H$ $h(s)$ is in the image of. Let $m_F$ be the number of edges of $H$ in $F$ which are incident to $s$. The probability that the next discovered edge does not connect to an inner vertex of some copy of $F$ is at most $(N\cdot {\mathrm{deg}}^H(s)-N\cdot m_F)/(N\cdot {\mathrm{deg}}^H(s))$. So the probability that a discovered edge satisfies our requirements, when drawing ${\mathrm{\Delta }}_H$ times, is at least $1-{\left(\frac{{\mathrm{deg}}^H(s)-m_F}{{\mathrm{deg}}^H(s)}\right)}^{{\mathrm{\Delta }}_H}={\mathrm{\Omega }}_H(1)$. $◀$

By applying Lemma 4.13 at most $|F|$ times, since $|F|$ bounds the diameter of $F$ from above. $◀$

Lemmas 4.14 and 4.15 makes it possible to simulate the behavior of Algorithm 2 inside a run of the RandomBoundedBFS. With breadth $\mathrm{\Delta }(H)$ and depth $|C|$ and probability ${\mathrm{\Omega }}_H(1)$, the output of RandomBoundedBFS contains a copy of $C$ in $G$ which is constructed just as in the algorithm. Transitions between parts is ensured by Lemma 4.14. $◀$

Fix a graph $G\in 𝒞$ which is $ϵ$-far from being $H$-free. We prove that there exists a constant $n=O_{ϵ,H,𝒞}(1)$ such that $\text{Tester}(n,H,ϵ,G)$ rejects with probability at least $2/3$. Since Tester starts by stripping isolated vertices from $H$, we assume that $H$ contains none. Let $n_H$ be the number of connected components of $H$. First, we use Lemmas 3.1, 4.2, 4.4, and 3.4 (in this order) to obtain a set $\mathscr{H}$ of cardinality ${\mathrm{\Omega }}_{ϵ,H,𝒞}(|V(G)|)$ such that $G[\mathscr{H}]$ is $c$-degree preserving and contains a uniformly-layered tree embedding³³3Note that having uniformly-layered tree embedding is a monotone property, so restricting further to get $c$-degree preserving is safe. (where $c=O_{ϵ,H,𝒞}(1)$).

Let $C$ be a connected component of $H$. We prove that the output of a single call to RandomBoundedBFS $(G[\mathscr{H}],|H|,\mathrm{\Delta }(H))$ contains a copy of $C$ compatible with the uniformly-layered tree embedding with probability ${\mathrm{\Omega }}_{ϵ,H}(1)$. By Lemma 4.16, it is sufficient to prove that RandomBoundedBFS starts on the copy of an inner vertex of $C$ with high probability. Since $C$ contains an edge, it cannot be reduced to a single source, and $C$ contains at least one inner vertex. As copies of inner vertices are in the image of precisely one copy of $H$, and as $G[\mathscr{H}]$ contains ${\mathrm{\Omega }}_{ϵ,H,𝒞}(|G|)$ copies of $H$, $G[\mathscr{H}]$ contains ${\mathrm{\Omega }}_{ϵ,H,𝒞}(|G|)$ vertices copies of inner vertices of $C$. Hence, RandomBoundedBFS $(G[\mathscr{H}],|H|,\mathrm{\Delta }(H))$ starts on an inner vertex of $C$ with probability ${\mathrm{\Omega }}_{ϵ,H,𝒞}(1)$.

Now, with Lemma 3.3, and the fact that $\mathscr{H}$ is $c$-degree preserving, we have that the output of a single call to RandomBoundedBFS $(G,|H|,\mathrm{\Delta }(H))$ contains a copy of $C$ compatible with the uniformly-layered tree embedding with probability ${\mathrm{\Omega }}_{ϵ,H,𝒞}(1)$ as well.

Each execution of the part of the algorithm which is repeated $n$ times (i.e. the $n_H$ calls to RandomBoundedBFS) finds a copy of $H$ with probability $p={\mathrm{\Omega }}_{ϵ,H,𝒞}(1)$ each time it is executed. Indeed, the $i$th connected component is found with probability ${\mathrm{\Omega }}_{ϵ,H,𝒞}(1)$ by the $i$th call to RandomBoundedBFS, in the form of a copy compatible with the uniformly-layered tree embedding, so these copies of the connected components of $H$ found with high probability are vertex disjoints and form a copy of $H$. Let $n$ be such that $2/n\le p$. Then, the probability that $\text{Tester}(n,H,ϵ,G)$ finds a copy of $H$ is at least $1-{(1-2/n)}^n>1-e^{-2}>2/3$. $◀$