= Branch set of a graph minor
= Branch sets of a graph minor
{synonym}
A <branch set of a graph minor> is the connected region representing one target <vertex>. For finite <simple graphs> $G$ and $H$, a witness to $H\preccurlyeq G$ assigns a nonempty <set> $B_x\subseteq V(G)$ to each $x\in V(H)$, such that the <sets> are pairwise disjoint, each <induced subgraph> $G[B_x]$ is a <connected graph>, and every $xy\in E(H)$ has a witnessing <edge> of $G$ between $B_x$ and $B_y$. Extra <edges> between <branch sets of a graph minor> are allowed: they can be deleted. Unused <vertices> are also allowed.<Minor Containment and Disjoint Paths in almost-linear time by Tuukka Korhonen and others>{ref}
\Image[/graph-minor-connected-branch-set-adjacency.png]
{title=Connected <branch sets of a graph minor> and their witnessing <edges>, with an optional <edge> deletion}
In the diagram, the host <graph> has <vertex set> $\{1,2,3,4,5,6\}$ and <edges>
$$
12,\ 34,\ 56,\ 23,\ 45,\ 61,\ 24.
$$
Choose $B_A=\{1,2\}$, $B_B=\{3,4\}$, and $B_C=\{5,6\}$. Their internal <edges> $12,34,56$ establish connectedness. The <edges> $23,45,61$ witness $AB,BC,CA$, respectively, so they form a model of the <complete graph> $K_3$. The additional <edge> $24$ also joins $B_A$ to $B_B$; it supplies another witness for the same target <edge>, not a fourth target <edge>. Contracting $12,34,56$ and merging duplicate <edges> gives exactly $\{AB,BC,CA\}$.
The same <branch sets of a graph minor> also witness the <path graph> $A,B,C$: retain the witnesses $23,45$, and delete $61$ to remove the unwanted $AC$ adjacency. This demonstrates why the definition requires an <edge> for every target adjacency, without forbidding other adjacencies in the host <graph>. For a <complete graph> $K_t$, there are no unwanted pairs: its model consists of $t$ disjoint connected <branch sets of a graph minor> with an <edge> between every pair.
To turn a model into an operation sequence, keep a <spanning tree> inside each $G[B_x]$, keep one witnessing <edge> for each <edge> of $H$, and delete all other <edges> and unused <vertices>. Contract each chosen <spanning tree> to one <vertex>. Disjointness prevents two target <vertices> from merging; connectedness provides the <edge contractions> that merge each individual region. Conversely, track the original <vertices> merged into every surviving <vertex> during a deletion-and-<edge contraction> sequence. They form disjoint connected <branch sets of a graph minor>, and each surviving <edge> comes from an original <edge> between its two regions. A list of these regions, their connecting <trees>, and their witnessing <edges> therefore gives a directly checkable certificate.
Back to article page
