# Two disjoint trees

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!

Here is a small example

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? $A_1$ consists of the two vertices labelled $1$.

$A_2$ consists of the three vertices labelled $2$.

$(A_1, A_2)$ is not independent because all the vertices labelled $3$ are required to connect $A_2$ and none would be left to connect $A_1$.

$(A_1, B_2)$ is independent for any $B_2 \subset A_2$ with $|B_2|=2$ because only two vertices labelled $3$ are required to connect any $B_2$, leaving the other free to connect $A_1$.

The graph is planar -- move one $1$ to the outer face.

I have no idea whether some simple kind of obstruction can be derived from such an example.

• Thank you very much for your example! It seems that you might as well remove the leaves and relabel $3 \to 2$ for the other three. (General reduction rule: if there is a cutvertex $v$ for which distinct components of $G - v$ meet $A_i$, then we may as well add $v$ to $A_i$ without changing dependency. If $v$ already lies in $A_j$, $j \neq i$, then the pair is necessarily dependent.) The resulting triple $(G', A_1', A_2')$ is a 'trivially dependent' example, since one of the two sets separates the other (the vertices of $A_1$ lie in distinct components of $G - A_2$). – monkeymaths Aug 16 '18 at 13:51
• Thank you for you kind words while I have been close to trivial! What about adding edges from all $1$'s to all $2$'s in my initial example? Then the $3$'s are not cutvertices anymore. Or is it an elementary reduction rule as well to remove any edge between $A_1$ and $A_2$? I'll look for yet another modification so as to exhaust all simple reduction rules. – Claude Chaunier Aug 16 '18 at 15:26
• Well, yes, edges between $A_1$ and $A_2$ are of no use when trying to find those trees, so this seems like a straightforward reduction rule. But finding a 'right' set of reduction rules which really gets you anywhere is part of the (wide open, at least to me) problem. – monkeymaths Aug 16 '18 at 19:59