Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ *independent* if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which *cover* the two sets in the sense that $A_1 \subseteq V(T_1)$, $A_2 \subseteq V(T_2)$.

(I) The problem I would like to pose is to characterise the independent pairs of sets of vertices. I am not aware of any existing literature on this problem and would be grateful for suitable pointers.

In the case where $|A_1| = |A_2| = 2$, a complete characterisation was given by Seymour ("Disjoint paths in graphs") and, independently, by Thomassen ("2-Linked Graphs"). Essentially, up to a reduction step, the pair $(\{x_1, y_1 \}, \{x_2, y_2\})$ is independent *unless* $G$ has a drawing in the plane with one face containing these four specified vertices in order $(x_1, x_2, y_1, y_2)$, which is an obvious *obstruction* to the existence of two disjoint trees covering the sets.

A complete characterisation of the general case might be out of reach, but I'm having a hard time even coming up with "new" obstructions which do not come from the consideration of just pairs of vertices.

*What are some good examples where $(A_1, A_2)$ is not independent, although for any $B_1 \subseteq A_1, B_2 \subseteq A_2$ with $|B_1| = |B_2|$, the pair $(B_1, B_2)$ is independent?*

(II) I am also interested in the following notion derived from the above. Call a set $A \subseteq V(G)$ *agile* if for every bipartition $A = A_1 \cup A_2$ of $A$, the pair $(A_1, A_2)$ is independent. It is easy to see that $V(G)$ is agile if and only if $G$ is a complete graph. As a somewhat different example, take a complete bipartite graph $K_{2,t}$. Then the set of all degree-2 vertices is agile.

The containment of a large agile set may be regarded as a measure of the complexity of a graph. If $H$ is a minor of $G$ and $H$ has an agile set $A$, then $G$ contains an agile set $A'$ with $|A'| \geq |A|$. Based on this, it is not hard to show that $G$ contains an agile set of order 4 if and only if $G$ is not outerplanar.

*Is there, for every integer $t$, an integer $m(t)$ such that every graph which contains an agile set of size at least $m(t)$ contains $K_{2,t}$ as a minor?*

I'd be happy about any sort of insights you can contribute to these questions as well as to pointers to relevant literature. Thank you very much in advance!