Rooted branch-set reduction ($m=h-q/2$)

Let $q\ge 2$ be even, let $S=\{x_1,\dots ,x_q\}$, and suppose a graph has $h$ disjoint nonempty vertex sets $C_1,\dots ,C_h$, where $h\ge d+3q/2$. Suppose each $G[C_i]$ is connected or every one of its graph components meets $S$, and each $C_i$ is adjacent to all but at most $d$ of the other $C_j$ not meeting $S$. Assume also that no rooted separation of a graph of order below $q$ avoids $d+1$ of these sets. Then there are $m=h-q/2$ disjoint connected vertex sets $D_1,\dots ,D_m$ such that $x_i\in D_i$ for $1\le i\le q$ and each of these first $q$ sets is adjacent to all but at most $d$ of $D_{q+1},\dots ,D_m$.

Here adjacency of sets means existence of an edge between them. A rooted separation of a graph is $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, no edges between $A\setminus B$ and $B\setminus A$, and order $|A\cap B|$. It avoids $C_i$ when $A\cap C_i=\varnothing$. We prove the reduction by induction, first on the vertex count and then on the edge count; any counterexample chosen minimal in this ordering will be impossible.

We may delete edges joining two vertices of $S$. They cannot affect rooted separations of a graph, since $S$ lies wholly on the first side. Within a branch set, their deletion can only split a graph component into graph components each containing an endpoint in $S$, so the branch-set hypothesis also persists. An isolated vertex outside $S$ and all branch sets can be deleted. An isolated vertex $v\in S$ is also impossible, since $(S,V(G)\setminus \{v\})$ has order $q-1$ and avoids at least $h-q\ge d+q/2\ge d+1$ sets. Thus in a minimal counterexample $S$ is independent, and every isolated vertex outside $S$ belongs to a singleton branch set.

Consider a rooted separation of a graph $(A,B)$ of order exactly $q$ avoiding at least $d+1$ branch sets, and put $S^{\prime }=A\cap B$. Restrict to $G^{\prime }=G[B]-E(G[S^{\prime }])$ and $C_i^{\prime }=C_i\cap B$. Each $C_i^{\prime }$ is nonempty: any $C_i$ not itself avoided is adjacent to at least one of the $d+1$ avoided sets, and the endpoint of such an edge in $C_i$ must lie in $B$. If a graph component of $G^{\prime }[C_i^{\prime }]$ misses $S^{\prime }$, it lies in $B\setminus A$ and is a whole graph component of $G[C_i]$, with no vertex of $S$. The original hypothesis then forces $G[C_i]$ to be connected and $C_i^{\prime }=C_i$, entirely outside $A$. Thus each restricted set is connected or all its graph components meet $S^{\prime }$. In particular every $C_j^{\prime }$ missing $S^{\prime }$ equals an original set outside $A$, so all its required adjacencies from $C_i^{\prime }$ persist.

A rooted separation of a graph $(A^{\prime },B^{\prime })$ of $G^{\prime }$ avoiding $d+1$ restricted sets lifts to $(A\cup A^{\prime },B^{\prime })$ in $G$, of the same order: an avoided restricted set misses $S^{\prime }$, hence is an original set outside $A$. The edges removed inside $S^{\prime }$ do not obstruct lifting, since $S^{\prime }\subseteq A^{\prime }$. This proves the required separation hypothesis for $G^{\prime }$. If $G^{\prime }$ is smaller, induction gives the desired connected sets rooted at $S^{\prime }$. Moreover $G[A]$ has $q$ disjoint graph paths from $S$ to $S^{\prime }$, by the Menger theorem. Indeed a separator of smaller order between these sets would give a rooted separation of a graph of $G$ of smaller order still avoiding those $d+1$ original sets. Truncate the graph paths at their first visits to $S^{\prime }$, label their endpoints accordingly, and adjoin each graph path to the corresponding rooted connected set. They meet $B$ only in their distinct endpoints, so this gives the desired sets for $G$, a contradiction. Consequently in a minimal counterexample every such separation of order $q$ has $B=V(G)$ and $A=S$, an independent set.

Now contract any edge whose endpoints do not belong to two different branch sets. Its endpoints cannot both lie in $S$, so the image of $S$ still has size $q$. The branch-set conditions persist. If the contraction created a forbidden rooted separation of a graph of order below $q$, its lift would have order below $q$, except possibly when the contracted vertex lies in its separator. In that case the lifted order increases by one and is at most $q$. Equality would put the contracted edge inside $A$, contradicting the just-proved independence of $A$ for an order-$q$ separation avoiding $d+1$ sets. Thus the separation hypothesis also persists. Applying induction in the contracted graph and expanding the contracted vertex would produce the required disjoint connected sets. Hence every edge in a minimal counterexample joins two different branch sets.

Every vertex outside the branch sets would be isolated, since every edge joins two branch sets; such an isolated vertex could be deleted. Thus the branch sets cover the graph. Each nonsingleton branch set is therefore an independent set, and all its vertices belong to $S$, because each of its singleton graph components must meet $S$. Let $C$ be the union of the nonsingleton branch sets, and write $c=|C|\le q$. There is a matching in a graph from $C$ into $V(G)\setminus S$. Otherwise the Hall marriage theorem gives $X\subseteq C$ with neighbourhood $Y\subseteq V(G)\setminus S$ satisfying $|Y|<|X|$. Since $S$ is independent, $(S\cup Y,V(G)\setminus X)$ is a rooted separation of a graph of order $q-|X|+|Y|<q$. It avoids every singleton branch set outside $S\cup Y$, of which there are at leastThe penultimate counting bound uses that the nonsingleton sets number at most $c/2$, so $|V(G)|-c\ge h-c/2$. This contradicts the separation hypothesis.

Use that matching in a graph to make a two-vertex connected set for each terminal in $C$; terminals outside $C$ remain singleton sets. There are at leastunused vertices, all singleton original branch sets. Choose $m-q$ of them for the remaining $D_i$. Every rooted $D_i$ contains a singleton original branch set: either its terminal, or its terminal's matched neighbour. That singleton misses at most $d$ of the selected nonterminal singleton sets. This constructs the desired family and completes the proof.