Proof of Theorem 5. Let \(K = K(rt,t)\) be the constant given by Lemma 3 and set \(R=R(K,t)\), where \(R(\cdot,\cdot)\) is the Ramsey number. Let \(c_t(\cdot)\) be the polynomial given by Lemma 2 and set \(c= c_t(s)\). We define \[\nu= 2Cc^{r+1}(R+1),\quad \text{ } \quad \tau = 11(2t)^2(2t+\nu+3)\binom{2t + \nu}{\nu}^2,\] \[\iota = c^{r+1}t\tau^R ,\quad \text{ and } \quad M(C, s,t,r) = \big(r^r512C\big(2\iota(R+1)\big)^r\big)^{2t^{2t}}.\] Note that the binomial term in \(\tau\) is bounded by \(\binom{2t+\nu}{\nu} \leq \frac{(2t+\nu)^{2t}}{(2t)!}\), which is polynomial in \(s\). Since \(\tau\) and \(c\) are polynomial in \(s\), we conclude that \(M\) is polynomial in \(s\).

We may assume that \(\alpha(Y) > M(C, s, t, r)\) as otherwise there is nothing to show. We proceed by induction on \(r\). When \(r=1\), the result follows from Lemma 1 with \(X = \emptyset\) and the observation that \(\alpha(N[z] \cap Y) = \alpha(N(z) \cap Y)\), unless \(N[z] \cap Y = z\) in which case \(z\notin Z\) since \(\frac{\alpha(Y)}{C} > 1\).

Now let \(r \in \N\), and assume that the result holds for \(1,\dots, r-1\). By definition of \(M\), we have \(\alpha(Y) > M(2C\iota (R+1), s, t, r-1)\). By the inductive hypothesis, there is a set \(X_{r-1}\) with \(\alpha(X_{r-1}) \leq M(2C\iota(R+1), s,t,r-1)\) for which \[Z_{r-1} = \left\{z\in V(G)\setminus X_{r-1} : \alpha(N_{G\setminus X_{r-1}}^{r-1}[z] \cap Y) \geq \frac{\alpha(Y)}{2\iota C(R+1)}\right\}\] has \(\alpha(Z_{r-1}) \leq M(2C\iota(R+1),s,t,r-1)\). Let \(X = Z_{r-1} \cup X_{r-1}\). Then, since \(r \geq 2\), \[\begin{align} \alpha(X) \leq 2 M(2C\iota(R+1),s,t,r-1) \leq M(C,s,t,r). \end{align}\]

[the32lemma32claim32cleaned32r-1] is a direct consequence of the definition of \(X\).
Let \[Z= \left\{z\in V(G)\setminus X : \alpha(N_{G \setminus X}^{r}[z] \cap Y) \geq \frac{\alpha(Y)}{C}\right\},\] we will show that \(\alpha(Z) \leq M(C,s,t,r)\). For the sake of a contradiction, suppose not. Let \(I\) be an independent subset of \(Z\) of size \(\iota\) which exists since \(M(C,s,t,r) \geq \iota\). Let \(Y_{r-1} = N_{G\setminus X}^{r-1}[I] \cap Y\). Set \(G' = G\setminus X\) and \(Y ' = Y \cap G'\). Then in \(G'\) there is no path of length less than \(r\) from \(I \cap G'\) to \(Y'\).

It follows from [the32lemma32claim32cleaned32r-1] that \[\begin{align} \alpha (N_{G'}^{r}(z) \cap Y') &\geq\alpha (N_{G\setminus X}^{r}[z] \cap Y) -\alpha (Y_{r-1}) \\ &> \frac{\alpha(Y)}{C} - |I| \cdot \frac{\alpha(Y)}{2C\iota (R+1)}\\ & \geq \frac{\alpha(Y)}{2C}. \end{align}\] In particular, for every \(z\in I\), there exist paths from \(z\) to \(Y'\) of length \(r\). This proves [claim32that32I32still32has32paths32to32Y39].
Since \(\mathcal{C}_t\) is hereditary and by 2, \(\chi(G') \leq c\). Fix a proper \(c\)-coloring of \(G'\). For a given path \(p_0-p_1-\dots-p_r\) of length \(r\) in \(G'\), we call the sequence of colors \((c(p_0), c(p_1), \dots, c(p_r))\) the type of the path. For every \(z\in I\) and every \(y\in Y' \cap N_{G'}^r(z)\), let \(P_{z,y}\) be a \((z,y)\)-path of length \(r\). For every \(z \in I\), let the type of \(z\) be the most common type among the paths in the set \(\left\{P_{z,y} : y\in Y' \cap N_{G'}^r(z) \right\}\) (breaking ties arbitrarily). Let \(T\) be the most common type among the vertices in \(I\) (again breaking ties arbitrarily). Let \(I'\subseteq I\) be the set of vertices of type \(T\), and let \(Y''\) be the set of vertices in \(Y'\) that can be reached by paths of type \(T\) from vertices in \(I'\). Let \(G''\) be the graph induced by the union of the \((I',Y'')\)-paths of type \(T\). We define the 0th level as \(L_0 = I'\) and the ith level as \(L_i = N^i_{G''}(I')\) for \(i \in [r]\). For \(v \in G''\), let \(l(v)\) be the integer \(i\) such that \(v \in L_i\).

The first assertion is immediate from the definition of \(I'\) and since there are at most \(c^{r+1}\) distinct possible types. The second assertion follows from [claim32that32I32still32has32paths32to32Y39] and the fact that \(z\) is of type \(T\). This proves [I3932properties].

By construction, the levels are disjoint, and every edge has its ends in two consecutive levels (since otherwise we would be able to find a path of length less than \(r\) between \(I'\) and \(Y''\)). It is sufficient to show that each level \(L_i\) is an independent set, as in this case, the set of even levels and the set of odd levels form a bipartition of \(G''\). Since \(\mathop{\mathrm{dist}}(I',Y'')=r\) and every vertex in \(G''\) is in an \((I',Y'')\)-path of length \(r\) of type \(T\), it follows that for every \(i\) and for every vertex \(v\in L_i\), there exists an \((I',v)\)-path of length \(i\) that is an initial segment of a path of type \(T\). Therefore, all the vertices of \(L_i\) belong to the same color class, which proves the first assertion of [claim32bipartite]. The second assertion follows since every bipartite graph in \(\mathcal{C}_t\) is \(K_{t,t}\)-subgraph-free.
For \(D \geq 0\), let \(\nu_D = \frac{2Cc^{r+1}(R+1)}{D+1}\) for any \(D\geq 0\). Note that \(\nu= \nu_0\).

Proof of Claim.. We proceed by induction on \(D\). When \(D=0\), the statement is vacuously true. Now, assume inductively that the result holds for \(1, \dots, D-1\).

By taking a subset if necessary, we may assume that \(|I^\star|=t\tau^D\). Let \(H\) be a hypergraph with vertex set \(Y^{\star}\) and hyperedge set \(I^{\star}\), where for every \(z\in I^{\star}\), the hyperedge \(e_z\) is defined as \(\{y\in Y^{\star} : y \in N^r_{G^{\star}}(z)\}\). See 1 for a visualization.

The proof proceeds by using 7 to find a vertex in \(Y^\star\) that is contained in the \(r\)-neighborhood of many vertices of \(I^\star\). We first show that \(\nu(H)\) and \(\lambda(H)\) are bounded by functions of \(t\) and \(\nu_D\).

Suppose not, then there are more than \(\nu_D\) pairwise disjoint subsets of \(Y^{\star}\), each with at least \(\frac{\alpha(Y)}{\nu_D}\) vertices. Therefore \[|Y^{\star}| > \frac{\alpha(Y)}{\nu_D} \cdot \nu_D = \alpha(Y).\] Since \(Y^{\star}\) is an independent set contained in \(Y\), this is a contradiction. This proves [No32large32matching].

Suppose that \(\lambda(H) \geq 2t\). We will obtain a contradiction by constructing a \(1\)-subdivision of \(K_{2t}\), from which we obtain a \(K_{t,t}\) induced minor. Let \(z_1,\dots,z_{2t}\) be vertices in \(I'\) such that the hyperedges \(e_{z_1},\dots,e_{z_{2t}}\) exhibit \(\lambda(H)\geq 2t\). For every \(i<j \in[2t]\), let \(y_{i,j}\) be a vertex in \((e_{z_i}\cap e_{z_j})\setminus\bigcup_{k\neq i,j} e_{z_k}\). We call \(y_{i,j}\) the private \(r\)-neighbor of \(z_i\) and \(z_j\). Let \(P_{i,j}\) and \(P_{j,i}\) be paths of length \(r\) from \(z_i\) to \(y_{i,j}\) and from \(z_j\) to \(y_{i,j}\), respectively, such that the union \(|P_{i,j}\cup P_{j,i}|\) is minimal. Let \(s_{i,j}\) be the vertex in \(P_{i,j}\cap P_{j,i}\) with \(l(s_{i,j})\) minimum. Such a vertex exists because \(y_{i,j} \in P_{i,j}\cap P_{j,i}\). We define \(P_{i,j}' = z_i -P_{i,j} -s_{i,j} \setminus s_{i,j}\) and \(R_{i} = \bigcup_{j\neq i}P_{i,j}'\).

Suppose not, then since \(|R_i \cup R_j|\geq 2\) and since \(R_i\) and \(R_j\) are each connected subgraphs, there is an edge \(e = u_iu_j\) with \(u_i\in P_{i,k}' \subseteq R_i\) and \(u_j \in P_{j,l}' \subseteq R_j\) for some \(k,l\). See Figure 2 for a visualization. Since for every edge \(e\) the ends of \(e\) belong to two consecutive levels, without loss of generality, \(u_i \in L_{m}\) and \(u_j\in L_{m-1}\) for some \(m \in [r]\). Now, \(z_j -P_{j,l}-u_j -u_i-P_{i,k}-y_{i,k}\) is a path of length \(r\) from \(z_j\) to \(y_{i,k}\). Since \(y_{i,k}\) is the private \(r\)-neighbor of \(z_i\) and \(z_k\), it follows that \(k=j\). Then \(u_i\) is a vertex in the intersection of a \((z_j,y_{i,j})\)-path and \(P_{i,j}\). Since \(u_i \in P_{i,j}'\), \(l(u_i) <l(s_{i,j})\), contradicting the minimality of \(s_{i,j}\). This proves [claim:32Ri32anticomplete].

Suppose that \(s_{i,j}\) is adjacent to a vertex \(u\in P_{k,l}\). Then \(|l(u)-l(s_{i,j})| =1\). First, suppose that \(s_{i,j} \in L_{m-1}\) and \(u \in L_m\) for some \(m \in [r]\). See the left-hand side of Figure 3. Then \(z_i-P_{i,j} -s_{i,j}\) and \(z_j-P_{j,i} -s_{i,j}\) are paths of length \(m-1\) and \(u-P_{k,l} -y_{k,l}\) is a path of length \(r-m\). Since \(s_{i,j}\) and \(u\) are adjacent, we have found a \((z_i, y_{k,l})\)-path and a \((z_j,y_{k,l})\)-path of length \(r\). Since \(y_{k,l}\) is the private \(r\)-neighbor of \(z_k\) and \(z_l\), we conclude that \(k\in\left\{i,j\right\}\).

Now suppose \(s_{i,j} \in L_{m}\) and \(u \in L_{m-1}\). See the right-hand side of Figure 3. Then \(z_k -P_{k,l} -u\) is a path of length \(m-1\) and \(s_{i,j}-P_{i,j} -y_{i,j}\) is a path of length \(r-m\). Since \(u\) and \(s_{i,j}\) are adjacent, \(z_k -P_{k,l} -u -s_{i,j}-P_{i,j} -y_{i,j}\) is a path of length \(r\) from \(z_k\) to \(y_{i,j}\), which implies that \(y_{i,j} \in e_{z_k}\). However, \(y_{i,j}\) is the private \(r\)-neighbor of \(z_i\) and \(z_j\), so we conclude that \(k\in\left\{i,j\right\}\). This proves [claim:32sij32does32not32see32stuff].

We now complete the proof of [No32large32lambda]. Consider the graph \(\Gamma\) obtained by deleting every vertex that is not in \((\bigcup_{i\in [2t]} R_i) \cup (\bigcup_{i<j \in[2t]}s_{i,j})\) and contracting each \(R_i\) to a single vertex \(r_i\). Then \(\Gamma\) is an induced minor of \(G\). By [claim:32Ri32anticomplete], the set \(\left\{r_i\right\}_{i\leq2t}\) is stable. In addition, [claim:32sij32does32not32see32stuff] implies that if \(k\notin \left\{i,j\right\}\), then \(s_{i,j}\) is not adjacent to any vertex in \(R_k\). Therefore, in \(\Gamma\), \(s_{i,j}\) is adjacent to \(r_k\) if and only if \(k\in \{i,j\}\). It also follows from [claim:32sij32does32not32see32stuff] that if \(\left\{k,l\right\} \neq \left\{i,j\right\}\), then \(s_{i,j}\) and \(s_{k,l}\) are not adjacent, so the set \(\bigcup_{i<j \in[2t]}s_{i,j}\) is stable. Therefore, \(\Gamma\) is a \(1\)-subdivision of a \(K_{2t}\), which contains a \(K_{t,t}\) induced minor, a contradiction. This completes the proof of [No32large32lambda].
By [No32large32matching], \(\nu(H) \leq \nu_D\) and by [No32large32lambda], \(\lambda (H)\leq 2t\). Note that \(\nu_D \leq \nu\). By 7, we have \[\tau(H) \leq 11(2t)^2\left(2t+ \nu_D +3 \right)\binom{2t + \nu_D}{\nu_D}^2 \leq \tau.\] Let \(\mathcal{T} \subseteq Y^{\star}\) be a hitting set of minimum size. Since \(|\mathcal{T}| \leq \tau\), there exists a vertex \(x \in \mathcal{T}\) such that the set \(\tilde{I}= \left\{z\in I^{\star} : x\in e_z\right\}\) has size \(|\tilde{I}| \geq \frac{1}{\tau}|I^{\star}|\). For each \(z\in \tilde{I}\), fix a \((z,x)\)-path \(Q_{z,x}\) of length \(r\). Then set \(\tilde{J}_D = \bigcup_{z\in \tilde{I}\;}(Q_{z,x} \setminus{z} )\).

Let \(\tilde{G} = \left(G^{\star}\setminus\left(\tilde{J}_D\cup I^{\star}\right)\right)\cup \tilde{I}\). We now check that, after deleting \(\tilde{J}_D\), every vertex in \(\tilde{I}\) still reaches a sufficiently large proportion of \(Y^\star\) via paths of length \(r\), which will allow us to apply induction.

Let \(z\in \tilde{I}\) and define \(\tilde{Y}_z = (N_{G^{\star}}^{r}(z) \cap Y^\star) \setminus(N_{G^{\star}}^{r-1}(\tilde{J}_D \cap L_1) \cap Y^\star)\). We show that \(\tilde{Y}_z\subseteq N^{r}_{\tilde{G}}(z) \cap Y^\star\). Let \(y \in \tilde{Y}_z\), then there is a \((z,y)\)-path \(P_{z,y}\) in \(G^{\star}\) of length \(r\). We show that every such path is vertex-disjoint from \(\tilde{J}_D\).

Suppose, for contradiction, that there exists \(u\in P_{z,y} \cap \tilde{J}_D\) with \(l(u)=m\) for some \(m\). Since \(u \in \tilde{J}_D\), there exist \(z'\in \tilde{I}\) (not necessarily distinct from \(z\)), and a path \(P_{z',x} \subseteq \tilde{J}_D\) such that \(u \in P_{z',x}\). Let \(v\) denote the vertex in \(P_{z',x} \cap L_1\). See Figure  4 for a visualization. Then \(v-P_{z',x}-u-P_{z,y}-y\) is a path of length \(r-1\) from \(v \in \tilde{J}_D \cap L_1\) to \(y\). This implies \(y \in N^{r-1}_{G^\star}(\tilde{J}_D \cap L_1)\cap Y^\star\), contrary to the assumption.

Therefore, the vertices in \(\tilde{Y}_z\) can only be reached from \(z\) via paths of length \(r\) that are vertex-disjoint from \(\tilde{J}_D\), which means that these paths are entirely contained in \(\tilde{G}\). We conclude that \(\tilde{Y}_z \subseteq N_{\tilde{G}}^r(z) \cap Y^\star\) and \[\begin{align} |N_{\tilde{G}}^r(z) \cap Y^\star| &\geq |N_{G^{\star}}^{r}(z) \cap Y^\star| - |N_{G^{\star}}^{r-1}(\tilde{J}_D \cap L_1) \cap Y^\star| \\ & \geq \frac{\alpha(Y)}{\nu_D} - |I^{\star}| \cdot \frac{\alpha(Y)}{2\iota C(R+1)}\\ &\geq \frac{\alpha(Y) (D+1)}{2c^{r+1}C(R+1)} - \frac{\alpha(Y)}{2c^{r+1}C(R+1)} \\ &\geq \frac{\alpha(Y)}{\nu_{D-1}}, \end{align}\] where the second inequality follows from [the32lemma32claim32cleaned32r-1] and the third inequality uses the fact \(\frac{|I^\star|}{\iota} \leq c^{-(r+1)}\). This proves [inductive32z32neighborhood32in32Y].
Observe that \(\tilde{G}\) is an induced subgraph of \(G^{\star}\) where \(\tilde{G} \cap I' = \tilde{I}\) and \(\tilde{G} \cap Y'' = Y^{\star} \setminus\{x\}\). By construction \(|\tilde{I}| \geq \frac{1}{\tau} |I^{\star}| \geq t\tau^{D-1}\) and by [inductive32z32neighborhood32in32Y] for each \(z\in \tilde{I}\) we have \(\alpha(N_{\tilde{G}}^{r}(z) \cap (Y^{\star} \setminus\{x\})) \geq \frac{\alpha(Y)}{\nu_{D-1}}\). Hence, by the inductive hypothesis, there exists a set \(S \subseteq \tilde{I}\) and disjoint induced subgraphs \(J_1, \dots, J_{D-1}\) of \(\tilde{G}\) such that

• \(|S| = t\),

• \(|J_i| \leq r t\) for all \(i\in [D-1]\),

• and \(S \subseteq N_{G''}(J_i)\).

Recalling that \(S \subseteq I^{\star}\), we let \(J_D\) be the subgraph of \(\tilde{J}_D\) induced by \(\bigcup_{z\in S\;} (Q_{z,x}\setminus\{z\})\). Now \(|J_D| \leq rt\) and \(S \subseteq N_{G''}(J_D)\). Moreover, for each \(i\leq D-1\), \(J_i\) is vertex-disjoint from \(J_D\) because it is an induced subgraph of \(\tilde{G}\). We conclude that the set \(S\) and \(J_1, \dots, J_D\) satisfy the required properties and Claim 9 is proven. ◻

Recall from [I3932properties] that \[|I'| \geq t\tau^R \quad \text{ and } \quad \alpha(N_{G''}^r(z) \cap Y'') \geq \frac{\alpha(Y) (R+1)}{2c^{r+1}C(R+1)} \geq \frac{\alpha(Y)}{\nu_R} \text{ for every } z\in I'.\] Therefore, we can apply Claim 9 to \(G''\) to obtain a set \(S \subseteq I'\) and disjoint induced subgraphs \(J_1, \dots, J_R\) such that \(|S|=t, |J_i|\leq rt\), and \(S \subseteq N_{G''}(J_i)\) for all \(i \in [R]\). See Figure 5 for a visualization. Let \(\Lambda\) be a graph with vertex set \(J_1, \dots, J_R\), where two distinct vertices \(J_i\) and \(J_j\) are adjacent if and only if \(J_i\) and \(J_j\) are not anticomplete in \(G''\).

For the sake of contradiction, suppose that \(\Lambda\) has a stable set of size \(t\). Then, reindexing if necessary, there are \(t\) disjoint pairwise anticomplete induced subgraphs \(J_1, \dots, J_t\) of \(G''\). Let \(\Gamma\) be the graph obtained by deleting all vertices except \(\left(\bigcup_{i=1}^t J_i\right) \cup S\) and contracting all the edges in each \(J_i\) to a vertex \(j_i\). Since \(J_i\) and \(J_j\) are anticomplete for \(i\neq j\), the set \(\bigcup_{i \in [t]}\{j_i\}\) is stable, and since \(S \subseteq N_{G''}(J_i)\), each \(j_i\) is complete to \(S\). Therefore, \(\Gamma\) is an induced minor of \(G\) isomorphic to \(K_{t,t}\), a contradiction. This proves [No32t32pairwise32disjoint32sets].
By Theorem 6, it follows that \(\Lambda\) contains a clique of size \(K\). Reindexing if necessary, there are \(K\) pairwise disjoint subsets \(J_1, \dots, J_{K}\) in \(G''\) such that there is at least one edge between any two sets. By Lemma 3, \(G''\) contains a \(K_{t,t}\) subgraph, which contradicts [claim32bipartite]. This completes the proof of 5. ◻

Proof. Let \(M'(C,s,t,r)\) be the function given by Theorem 5, which is polynomial in the parameters \(s\) and \(C\). By Lemma 2, there is a polynomial \(p_t\) such that \(\chi(G) \leq p_t(s)\). Set \(M(C,s,t,r) = p_t(s) \cdot M'(Cp_t(s),s,t,r)\), which is polynomial in \(s\) and \(C\). We may assume that \(|Y| > M(C,s,t,r)\), as otherwise there is nothing to show.

By Theorem 5, there is a set \(X \subseteq V(G)\) with \(\alpha(X) \leq M'(Cp_t(s),s,t,r)\) such that if we define \[Z_\alpha = \left\{z\in V(G)\setminus X \colon \alpha(N^{r}_{G\setminus X}[z]\cap Y) \geq \frac{\alpha(Y)}{p_t(s)C}\right\}\] then \(\min(\alpha(Z_\alpha), \alpha(Y) )\leq M'(Cp_t(s),s,t,r)\). Since \(\alpha(Y )>M'(Cp_t(s),s,t,r)\), it follows that \(\alpha(Z_\alpha) \leq M'(Cp_t(s),s,t,r)\).

Let \[Z = \left\{z\in V(G)\setminus X \colon |N^{r}_{G\setminus X}[z]\cap Y| \geq \frac{|Y|}{C}\right\}.\]

We show that \(X\) and \(Z\) satisfy the conclusion of Theorem 10. Let \(z\in Z\) then, by Observation 8, it holds that \[\chi(N^r_{G\setminus X}[z] \cap Y)\cdot \alpha(N^r_{G\setminus X}[z] \cap Y) \geq |N^r_{G\setminus X}[z] \cap Y| \geq \frac{|Y|}{C}\geq \frac{\alpha(Y)}{C}.\] Since \(N^r_{G\setminus X}[z] \cap Y\) is an induced subgraph of \(G\), it has chromatic number at most \(p_t(s)\). Rearranging the inequality yields \[\alpha(N^r_{G\setminus X}[z] \cap Y) \geq \frac{\alpha(Y)}{p_t(s) C},\] and we conclude that \(Z \subseteq Z_\alpha\).

By Observation 8, we conclude \[|Z| \leq |Z_\alpha| \leq \chi(Z_\alpha) \cdot \alpha(Z_\alpha) \leq p_t(s)\cdot M'(Cp_t(s),s,t,r) \leq M(C,s,t,r)\] and \[|X| \leq \chi(X) \cdot \alpha(X) \leq p_t(s)\cdot M'(Cp_t(s),s,t,r) \leq M(C,s,t,r),\] as required. ◻

Proof. Let \(f(Cs)= 2M(Cs,Cs,t,r)\) where \(M\) is defined as in 10, let \(X'\) be obtained by 10 and let \(Z\) be the corresponding set, and let \(K\in \left\{Y,Z\right\}\) such that \(|K|\leq M(C,s,t,r)\). Let \(X=X'\cup K\); then \(|X|\leq f(Cs)\). If \(K=Y\) then \(|N^{r}_{G\setminus X}[v]\cap Y|=0\), otherwise, \(K=Z\) and therefore \(|N^{r}_{G\setminus X}[v]\cap Y| \leq \frac{|Y|}{C}\) for every \(v\in G\setminus X\). ◻

Proof. We proceed by induction on \(|V(G)|\). Let \(\hat{G}\) be a minimum \(r\)-cover of \(G\). If \(G\) is \((24f(8ks),r)\)-coverable, then the tree decomposition of \(G\) where \(V(G)\) is in a single bag satisfies the statement. Therefore, we may assume that \(|\hat{G}| > 24f(8ks)\). Note that if \(|V(G)|\leq 24f(8ks)\), then we immediately have that \(G\) is \((24f(8ks),r)\)-coverable, which proves the base case of the induction.

By adding vertices to \(\hat{Y}\) if necessary, we may assume that \(|\hat{Y}| = 12f(8ks)\). Note that \(|\hat{G}| > \frac{|\hat{Y}|}{2}\). Let \(Z_G\) and \(Z_Y\) be the sets obtained by applying [theLemma] to both \(\hat{Y}\) and \(\hat{G}\) with the parameters \(C=8k\) and \(r'=2r\). Let \(Z = Z_G \cup Z_Y\), \(G' = G \setminus Z\), \(\hat{G}' = \hat{G} \setminus Z\), and \(\hat{Y}' = \hat{Y} \setminus Z\). Then, \(|Z|\leq 2f(8ks)\) and for every \(v \in V(G')\), we have that \[\left|N^{2r}_{G'}[v] \cap \hat{Y}' \right| \leq \frac{|\hat{Y}|}{8k} \quad \text{ and } \quad \left|N^{2r}_{G'}[v] \cap \hat{G}' \right| \leq \frac{|\hat{G}|}{8k}.\]

Since \(G'\) is an induced subgraph of \(G\), \(G'\) admits \((k,r)\)-balanced separators. Therefore, by taking the union of two such separators, there exists \(\hat{S}\) such that \(|\hat{S}|\leq 2k\) and \(S=N_{G'}^r[\hat{S}]\) is a balanced separator of both \(\hat{G'}\) and \(\hat{Y}'\) in \(G'\). Let \(\hat{Y}_S = \hat{Y}'\cap N^{2r}_{G'}[\hat{S}]\) and \(\hat{G}_S = \hat{G}'\cap N^{2r}_{G'}[\hat{S}]\). Then \[|\hat{Y}_S| \leq 2k\cdot \frac{|\hat{Y}|}{8k} = \frac{|\hat{Y}|}{4} \quad \quad \text{ and } \quad \quad |\hat{G}_S| \leq 2k \cdot \frac{|\hat{G}|}{8k} = \frac{|\hat{G}|}{4}.\]

Let \(C\) be a connected component of \(G' - S =G-(Z\cup S)\). Define \[\begin{align} &C^\star = G \big[C \cup S \cup Z \cup N^{r}_{G'}[\hat{Y}_S] \big] \quad \quad \text{and} \quad \quad \hat{Y}^\star = (C \cap \hat{Y} ) \cup \hat{S} \cup Z \cup \hat{Y}_S. \end{align}\]

Observe that \(\hat{Y}^\star \subseteq V(C^\star)\). Next, we verify that \(C^\star\) and \(\hat{Y}^\star\) are suitable for the induction hypothesis.

Since \(\hat{G}\) was chosen to be a minimum \(r\)-cover of \(G\), in order to prove [claim:32C94star32is32not32all32of32G], it suffices to prove that \(C^\star\) can be covered by fewer than \(|\hat{G}|\) balls of radius \(r\). We check that balls centered on \[\hat{C}^\star = (C \cap \hat{G} ) \cup \hat{S} \cup Z \cup \hat{G}_S \cup \hat{Y}_S\] have the required property. Since \(S\) is a balanced separator for \(\hat{G}\), we have \[\begin{align} |\hat{C}^\star| \leq |V(C) \cap \hat{G}| + |\hat{S}| + |Z| + |\hat{G}_S| + |\hat{Y}_S| \leq \frac{1}{2}|\hat{G} | + 2k + 2f(8ks) + \frac{|\hat{G}|}{4} +\frac{|\hat{Y}|}{4} < |\hat{G}|. \end{align}\] In the last inequality, we used that \(f(x)\geq x\).

Now it remains to check that \(V(C^\star) \subseteq N^{r}_G[\hat{C}^\star]\). See Figure 6 for a visualization. Suppose for a contradiction that \(v \in C^\star\) but \(v\notin N^{r}_G[\hat{C}^\star]\). If \(v\in S \cup Z\cup N_{G'}^r[\hat{Y}_S]\), then evidently \(v\in N^r_G[C^\star]\), and so we may assume \(v \in C\). Since \(G \subseteq N^r_G[\hat{G}]\), there exists \(u\in \hat{G}\) such that \(\mathop{\mathrm{dist}}_G(u,v) \leq r\). If \(u \in C\), then we are done, so we may assume \(u \notin C\). Since \(C\) is a component of \(G - (Z \cup S)\), there is a \((v,u)\)-path \(P_{v,u}\) of length at most \(r\) intersecting \(S \cup Z\). If there exists a vertex \(x \in P_{v,u} \cap Z\), then \(\mathop{\mathrm{dist}}(v, x) \leq r\) and so \(v \in N^r_G[Z]\), which is a contradiction. Therefore, \(P_{v,u}\cap S\) is non-empty. This implies that \(\mathop{\mathrm{dist}}_{G'}(u,\hat{S}) \leq \mathop{\mathrm{dist}}_{G'}(u,S) + r \leq 2r\) and we deduce that \(u \in \hat{G}_S\), and so \(v \in N^r_G[\hat{G}_S]\). This contradiction proves [claim:32C94star32is32not32all32of32G].

Since \(S\) is a balanced separator for \(\hat{Y}\), we can bound \(|\hat{Y}^\star|\) as follows: \[\begin{align} |\hat{Y} ^\star| &\leq |V(C) \cap \hat{Y}| + |\hat{S}| + |Z| + |\hat{Y}_S|\\ &\leq \frac{1}{2}|\hat{Y} | + 2k + 2f(8ks) + \frac{|\hat{Y}|}{4}\\ &< \frac{3|\hat{Y}|}{4} + 3f(8ks) \leq 12f(8ks) =|\hat{Y} |. \end{align}\] Now suppose that \(C_1, \dots, C_m\) are the components of \(G -(Z\cup S)\). By the inductive hypothesis, for every \(i \in [m]\), the graph \(C_i^\star\) admits a tree-decomposition \(\mathcal{T}_i=(T_i, \beta_i)\) such that every bag is internally \((24f(8ks),r)\)-coverable and there exists a bag \(\beta_i(t_i)\) that contains \(N^{r}_{C^\star_i}[\hat{Y}^\star_i]\).

Let \(T\) be obtained from the disjoint union of \(T_1, \dots, T_m\) by adding a new vertex \(t_0\) that is adjacent to \(t_1, \dots, t_m\). Define \(\beta(t) = \beta_i(t)\) for all \(t\in T_i\) and \(i\in [m]\), and set \(\beta(t_0) = N^{r}_G[\hat{Y}] \cup S\cup Z\). Then \(\mathcal{T}=(T,\beta)\) is a tree decomposition of \(G\). To see this, note that for any \(i<j \in [m]\) it holds that \(C_i^\star \cap C_j^\star \subseteq N_G^r[\hat{Y}_S] \cup S\cup Z\), which is contained in the bag \(\beta(t_0)\).

We observe that the set \(N^r_G[\hat{Y}] \cup S \cup Z\) can be \(r\)-covered by the set \(\hat{Y} \cup \hat{S} \cup Z\), which has at most \(12f(8ks) + 2k + 4f(8ks) \leq 24f(8ks)\) vertices. Since the other bags do not change, every bag of \(\mathcal{T}\) is internally \((24f(8ks), r)\)-coverable and \(\mathcal{T}\) has a bag containing \(N_G^r[\hat{Y}]\), as required. ◻