Linked graph

A graph is $k$-linked when any $2k$ distinct vertices paired as $(x_i,y_i)$ can be joined by $k$ mutually vertex-disjoint paths from $x_i$ to $y_i$.

Unlike vertex connectivity, linkage specifies all endpoint pairings simultaneously.

On vertices $0,\dots ,7$, join cyclic indices differing by one or two modulo eight. The resulting planar graph has a square face bounded in order by $0,2,4,6$. Deleting at most three vertices cannot disconnect it: each break in the surviving cyclic chain requires two consecutive deleted vertices, and two separate breaks require four deletions. It is therefore four-connected. Disjoint paths joining $0$ to $4$ and $2$ to $6$ would cross in the complementary disk of the square face, contrary to the Jordan curve theorem. Thus four-connectivity does not guarantee two-linkage.

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|\ge 2d+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.