= Solution
A <linked graph> is $k$-linked if it has at least $2k$ <vertices> and, for every choice of distinct terminals $s_1,\ldots,s_k,t_1,\ldots,t_k$, it has pairwise vertex-disjoint <graph paths> joining $s_i$ to $t_i$ for all $i$. The pairing is prescribed, which is stronger than the unpaired conclusion of the <Menger theorem>.
We prove the <rooted dense minor linkage> step carefully. We first prove the <rooted branch-set reduction>. 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 exactly the desired family, contradicting minimality and proving the branch-set reduction.
Return to the given $22k$-connected <graph>. By the allowed assumption it has a <graph minor> $H$ with $2\delta(H)\ge h+4k-1$, where $h=|H|$. Put $d=h-1-\delta(H)$. Then
$$
h\ge2d+4k+1.
$$
Take a branch-set model of $H$ and the $2k$ prescribed terminals as $S$. The branch <sets> are connected and each misses at most $d$ of the others. The separation hypothesis holds with $q=2k$: a separation of order below $2k$ avoiding a branch <set> would separate a surviving terminal from that <set>, contrary even to $2k$-connectivity. Since $h\ge d+3k$, the reduction applies. It produces $m=h-k$ <sets> with $s_i\in D_i$, $t_i\in D_{k+i}$, each terminal <set> missing at most $d$ of the $m-2k$ nonterminal <sets>. For each pair $D_i,D_{k+i}$ at least
$$
m-2k-2d=h-3k-2d\ge k+1
$$
nonterminal <sets> are adjacent to both. Choose different such <sets> for the $k$ pairs successively. The <connected graph> property inside the three <sets> and the two joining <edges> give a <graph path> from $s_i$ to $t_i$; take a simple <graph path> within their union. Different <graph paths> use disjoint <sets>. We have proved
$$
\boxed{\kappa(G)\ge22k\ \Longrightarrow\ G\text{ is }k\text{-linked}.}
$$
In fact the argument proves the stronger transfer statement with $2k$-connectivity and the stated dense <graph minor>.
For the negative assertion, it suffices to give a value of $k$ for which the proposed general implication fails. Take $k=2$ and the <graph> on cyclic indices $0,\ldots,7$ in which two indices are adjacent when their cyclic distance is one or two. This is the <four-connected planar obstruction to two-linkage>. Draw the even <cycle in a graph> $0,2,4,6$ as the outer square, the odd <cycle in a graph> $1,3,5,7$ as an inner square rotated by $45$ <degrees of vertices>, and join each odd <vertex> to the two neighbouring even <vertices>; the annulus is triangulated without crossings. The outer face has <vertices> $0,2,4,6$ in this order.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2002/iii/paper-9-antiprism.png]
{title=A four-connected planar graph with alternating terminal pairs on a square face}
Deleting at most three <vertices> leaves the <graph> connected. In cyclic order, consecutive surviving <vertices> are joined unless separated by a run of at least two deleted <vertices>. Disconnection requires two distinct such runs, hence at least four deletions. Conversely deleting the four <neighbours> of a <vertex> isolates it, so the <vertex connectivity> is exactly four. Disjoint <graph paths> joining $0$ to $4$ and $2$ to $6$ cannot exist: both would lie in the closed disk complementary to the outer face, and their endpoints alternate on its boundary. A first such <graph path> is a crosscut of the disk; the <Jordan curve theorem> puts the other two endpoints on opposite sides, forcing the second <graph path> to meet it. Thus
$$
\boxed{\kappa(G)=4=3\cdot2-2,\qquad G\text{ is not }2\text{-linked}.}
$$
This is a counterexample to the unrestricted implication; no claim that the same construction works for every $k$ is needed.
Back to article page
