= Rooted branch-set reduction
{title2=$m=h-q/2$}
Let $q\ge2$ be even, let $S=\{x_1,\ldots,x_q\}$, and suppose a <graph> has $h$ disjoint nonempty <vertex> <sets> $C_1,\ldots,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,\ldots,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},\ldots,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'=A\cap B$. Restrict to $G'=G[B]-E(G[S'])$ and $C'_i=C_i\cap B$. Each $C'_i$ 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'[C'_i]$ misses $S'$, 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=C_i$, entirely outside $A$. Thus each restricted <set> is connected or all its <graph components> meet $S'$. In particular every $C'_j$ missing $S'$ equals an original <set> outside $A$, so all its required adjacencies from $C'_i$ persist.
A <rooted separation of a graph> $(A',B')$ of $G'$ avoiding $d+1$ restricted <sets> lifts to $(A\cup A',B')$ in $G$, of the same order: an avoided restricted <set> misses $S'$, hence is an original <set> outside $A$. The <edges> removed inside $S'$ do not obstruct lifting, since $S'\subseteq A'$. This proves the required separation hypothesis for $G'$. If $G'$ is smaller, <induction> gives the desired connected <sets> rooted at $S'$. Moreover $G[A]$ has $q$ disjoint <graph paths> from $S$ to $S'$, 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'$, 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 \b[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 least
$$
|V(G)|-q-|Y|\ge |V(G)|-q-c+1\ge h-\frac c2-q+1\ge h-\frac{3q}2+1\ge d+1.
$$
The 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 least
$$
|V(G)|-q-c\ge h-\frac{3q}2=m-q
$$
unused <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.
Back to article page
