= Rooted dense minor linkage
{title2=$2\delta(H)\ge |H|+4k-1$}
If a <graph> is $2k$-connected and has a <graph minor> $H$ satisfying $2\delta(H)\ge |H|+4k-1$, it is $k$-linked. Write $d=|H|-1-\delta(H)$, so $|H|\ge2d+4k+1$. The <rooted branch-set reduction> replaces the minor model by $|H|-k$ disjoint connected sets, the first $2k$ containing any prescribed terminals separately, each missing at most $d$ of the remaining sets. Every prescribed pair then has at least $k+1$ common adjacent unused sets, allowing the $k$ connections to be selected successively. The reduction uses <rooted separations of a graph>, contraction of edges outside distinct branch sets, and a final <Hall marriage theorem> matching; the separation condition prevents a contraction from destroying access to the model.
Back to article page
