Proof of Theorem 2 .  We prove the following strengthening of Theorem2: Let $G$ be a graph, let $c$ be a positive integer, let $t_1\leqslant \cdots \leqslant t_c$ be non-negative integers, let $T_1,\ldots, T_c$ be trees with $|V(T_i)|=t_i$ for every $i\in [c]$ , let $x_1,\ldots, x_c$ be non-negative integers, at least one of which is non-zero, and let $I\,:\!=\, \{i\in [c]\mid x_i \geqslant 1\}$ . Then either

1. 1. $G$ contains pairwise vertex-disjoint subgraphs $\{M_{i, j}\mid i\in [c],\, j\in [x_i]\}$ such that, for each $i\in [c]$ and $j\in [x_i]$ , $M_{i,j}$ contains a $T_i$ minor, or

2. 2. there exists $X\subseteq V(G)$ with $|X|\leqslant \sum _{i\in I}x_it_i - t_{\max (I)}$ and $G-X$ does not contain $T_i$ as a minor for some $i\in I$ .

We call the tuple $(G,c,T_1,\ldots, T_c,x_1,\ldots, x_c)$ an instance. Theorem2 follows by letting $T_1,\ldots, T_c$ be the components of the forest $F$ and letting $x_1=x_2=\cdots =x_c=k$ .

Roughly, the proof describes an inductive procedure that attempts to find a pairwise disjoint collection of models, where the number of models of each tree $T_i$ is $x_i$ . Induction is on the number $\sum _{i\in [c]} x_i$ of models still missing from the collection. Failing to find one of the missing models at some step will establish (2).

Let $(G,c,T_1,\ldots, T_c,x_1\ldots, x_c)$ be an instance, and let $m\,:\!=\,\min (I)$ . Then $T_m$ is a smallest tree among $T_1,\ldots, T_c$ such that $x_m \geqslant 1$ , that is, such that we are still missing a model of $T_m$ . In the base case, $\sum _{i\in [c]} x_i=x_{m}=1$ , and either $G$ has a $T_{m}$ minor and the first outcome of the statement holds, or $G$ has no such minor and the second outcome holds with $X\,:\!=\,\varnothing$ , since $\sum _{i\in I} x_it_i -t_{\max (I)}= t_m - t_m = 0$ .

For the inductive case, assume that $\sum _{i\in [c]} x_i \geqslant 2$ and that the statement holds for instances with smaller values of the sum. If, for every $i\in I$ , $G$ has no $T_i$ minor, then the second outcome of the statement holds with $X\,:\!=\,\varnothing$ again. Thus, we may assume that $G$ has a $T_i$ minor for some $i\in I$ .

If $G$ has pathwidth at least $t_{m}-1$ , apply Lemma4 with $t=t_{m}$ and $F=T_{m}$ , and let $Y$ be the resulting subset of vertices of $G$ . If $G$ has pathwidth less than $t_{m}-1$ , simply let $Y\,:\!=\,V(G)$ . In either case, $G[Y]$ has pathwidth at most $t_m-1$ and has a path decomposition $(B_1, B_2, \dots, B_q)$ with $|B_\ell |\leqslant t_{m}$ for all $\ell \in [q]$ , and such that $\partial _G Y \subseteq B_q$ . See Figure 1. Furthermore, observe that in both cases $G[Y]$ has a $T_i$ minor for some $i\in I$ , by our assumption on $G$ .

Figure 1.

The set $Y$ and the graph $G_\ell$ whose boundary in $G$ is contained in $B_\ell$ .

Let $\ell \in [q]$ be the smallest index such that $G_\ell \,:\!=\,G[B_1 \cup \cdots \cup B_\ell ]$ contains a $T_{i}$ minor for some $i\in I$ , and let $i^{\prime}$ be an index in $I$ such that

(⋆) \begin{equation} G_\ell \textrm{ contains a } T_{i^{\prime}} \textrm{minor.} \end{equation}

Observe that

(⋆⋆) \begin{equation} G_\ell -B_\ell \textrm{ has no } T_i \textrm{ minor for every } i\in I. \end{equation}

We claim that

(⋆⋆⋆) \begin{equation} \textrm{ there is no edge in } G \textrm{ between vertices of } G_\ell -B_\ell \textrm{ and vertices of } G-V(G_\ell ). \end{equation}

To see this, suppose for a contradiction that $uv$ is such an edge, with $u\in V(G_\ell )-B_\ell$ and $v\in V(G)-V(G_\ell )$ . First, note that $u\in B_1 \cup \cdots \cup B_{\ell -1}$ . If $v\in Y$ , then $u$ and $v$ appear together in some bag $B_j$ of the path decomposition $(B_1, B_2, \dots, B_q)$ of $G[Y]$ , and $j \gt \ell$ since $v \notin B_1 \cup \cdots \cup B_\ell$ . However, since $u\in B_1 \cup \cdots \cup B_{\ell -1}$ and $u\in B_j$ , we conclude that $u$ belongs also to $B_\ell$ , a contradiction. If $v\notin Y$ , then $u\in \partial Y$ , and thus $u\in B_q$ . Again, we deduce similarly that $u \in B_\ell$ , a contradiction. This completes the proof of (⋆⋆⋆).

Let $G^{\prime}\,:\!=\,G - V(G_\ell )$ . Let $x^{\prime}_i \,:\!=\, x_i$ for each $i\in [c]-\{i^{\prime}\}$ and let $x^{\prime}_{i^{\prime}} \,:\!=\, x_{i^{\prime}}-1$ . Let $I^{\prime}=\{i\in [c]\mid x^{\prime}_i\geqslant 1\}$ . Apply induction to the instance $(G^{\prime},c,T_1,\ldots, T_c,x^{\prime}_1,\ldots, x^{\prime}_c)$ . If it results in a set of vertex-disjoint subgraphs $\{M^{\prime}_{i,j}\mid i\in [c],\, j\in [x^{\prime}_i]\}$ , with $M^{\prime}_{i,j}$ containing a $T_i$ minor for each $i\in [c]$ and $j \in [x^{\prime}_i]$ , then we let $M_{i,j}\,:\!=\,M^{\prime}_{i,j}$ for each $i\in [c]$ and $j \in [x^{\prime}_i]$ , and $M_{i^{\prime},x_{i^{\prime}}} \,:\!=\, G_\ell$ , which using (⋆) results in the desired collection of vertex-disjoint subgraphs. Otherwise, we obtain a set $X^{\prime}$ of at most $\sum _{i\in I^{\prime}}x^{\prime}_it_i -t_{\max (I^{\prime})}$ vertices such that $G^{\prime}-X^{\prime}$ does not contain $T_a$ as a minor for some $a\in I^{\prime}$ .

Let $X\,:\!=\,X^{\prime}\cup B_\ell$ . Observe that

\begin{align*} |X| = |X^{\prime}|+|B_{\ell }| &\leqslant \sum _{i\in I^{\prime}}x^{\prime}_it_i - t_{\max (I^{\prime})} + t_{m} \leqslant \sum _{i\in I}x_it_i - (t_{\max (I^{\prime})} + t_{i^{\prime}} - t_{m})\\ &\leqslant \sum _{i\in I}x_it_i - t_{\max (I)}. \end{align*}

To see why the last inequality holds, there are two cases to consider: (i) if $\max (I^{\prime})=\max (I)$ , then the inequality follows immediately since $t_{i^{\prime}}\geqslant t_m$ . (ii) If $\max (I^{\prime})\lt \max (I)$ , then $i^{\prime}=\max (I)$ and $\max (I^{\prime})\geqslant \min (I^{\prime})=m$ , so $t_{\max (I^{\prime})}+t_{i^{\prime}}-t_m \geqslant t_{i^{\prime}}=t_{\max (I)}$ .

Now, let us show that $G-X$ does not contain $T_i$ as a minor, for some $i\in I$ . Let $a\in I^{\prime}$ be such that $G^{\prime}-X^{\prime}$ does not contain $T_a$ as minor. We will show that we can take $i=a$ . To do so, it is enough to show that $X$ meets every inclusion-wise minimal subgraph of $G$ containing a $T_a$ minor. Let $M$ be such a subgraph of $G$ . Note that $M$ is connected, since $T_a$ is connected. Now, observe that by (⋆⋆⋆), either $M$ is contained in $G^{\prime}$ , or $M$ is contained in $G_\ell -B_\ell$ , or $M$ contains a vertex of $B_\ell$ . In the first case, $M$ contains a vertex of $X^{\prime}\subseteq X$ , by the choice of $a$ . The second case is ruled out by (⋆⋆). In the third case, $M$ contains a vertex of $B_\ell \subseteq X$ . Thus, we conclude that $M$ contains a vertex of $X$ . This concludes the proof.

Proof of Corollary 3 .  It is known (and an easy exercise to show) that, for every positive integer $p$ , the complete ternary tree $T_p$ of height $p$ has pathwidth $p$ . First, apply Theorem1 on $G$ with the tree $T_p$ . If $G$ contains $k$ vertex-disjoint subgraphs each containing a $T_p$ minor, we are done. So we may assume that the theorem produces a set $X_1$ of at most $|V(T_p)|(k-1) \leqslant 3^{p+1}(k-1)$ vertices such that $G-X_1$ has no $T_p$ minor.

By Lemma4, $G-X_1$ has a path decomposition $(B_1, B_2, \dots, B_q)$ of width strictly less than $3^{p+1}$ . It is easily checked that every inclusion-wise minimal subgraph of $G-X_1$ with pathwidth at least $p$ is connected. Apply Lemma5 on $G-X_1$ with the path decomposition $(B_1, B_2, \dots, B_q)$ , with $d=k$ , and with the family $\mathcal{F}$ of connected subgraphs of $G-X_1$ with pathwidth at least $p$ . If $\mathcal{F}$ contains $k$ pairwise vertex-disjoint members, we are done. So we may assume that the lemma produces a set $X_2$ of at most $3^{p+1}(k-1)$ vertices such that $X_2$ hits every member of $\mathcal{F}$ . It follows that $G-X_1-X_2$ has pathwidth strictly less than $p$ . Let $X\,:\!=\, X_1 \cup X_2$ . Since $|X| \leqslant 3^{p+1}(k-1) + 3^{p+1}(k-1) \leqslant 2\cdot 3^{p+1}k$ , the set $X$ has the desired properties.