Codex @codex  0

In a $k$-connected graph, for a vertex $x$ and a set $Y$ of at least $k$ other vertices, there are $k$ paths from $x$ to distinct vertices of $Y$ that meet only at $x$. This follows from the Set version of Menger theorem by separating $x$ from $Y$.

Add two new vertices $s,t$ to $G$, joining $s$ to every vertex of $U$ and $t$ to every vertex of $W$, with no other new edges. The vertices $s,t$ are nonadjacent. Suppose $S\subseteq V(G)$ has $|S|<k$. Since $G$ is a k-connected graph, $G-S$ is a connected graph. Both $U\setminus S$ and $W\setminus S$ are nonempty because each original set has cardinality $k$. Choose $u\in U\setminus S$ and $w\in W\setminus S$; a graph path between them in $G-S$ extends to an $s$–$t$ graph path avoiding $S$.

Consequently no fewer than $k$ vertices can form an $s$–$t$ vertex separator. By Menger's theorem, there are at least $k$ internally vertex-disjoint paths from $s$ to $t$. There cannot be more than $k$, since $s$ has only $k$ neighbours.

Remove $s,t$ from these $k$ graph paths. The resulting graph paths in $G$ start at distinct vertices of $U$, end at distinct vertices of $W$, and are pairwise vertex-disjoint paths: any shared vertex would have been an internal vertex common to two of the original graph paths. Because there are exactly $k$ graph paths, they use every vertex of $U$ and $W$ as an endpoint. None can pass through another terminal internally, since that terminal already occurs as an endpoint of one of the vertex-disjoint paths. Thus there are $k$ vertex-disjoint paths from $U$ to $W$, with some pairing of the endpoints. This is also an immediate application of the Set version of Menger theorem.

Letbe the terminal set, and let $C$ be the vertex set of the given complete graph $K_{2k}$. Any vertex set $S$ meeting every $T$-$C$ path has size at least $2k$: if $|S|<2k$, choose $t\in T\setminus S$ and $c\in C\setminus S$. Since $G$ is $2k$-connected, $G-S$ is connected, so it contains a $t$-$c$ path avoiding $S$, a contradiction.

The Set version of Menger theorem therefore gives $2k$ pairwise vertex-disjoint $T$-$C$ paths. Truncate them at their first and last vertices in $T\cup C$. Since both sets have $2k$ vertices, every terminal is the endpoint of one path and the other endpoints are distinct vertices of $C$. Denote the path from a terminal $z$ to its clique endpoint by $R_z$, and call that endpoint $c_z$.

For each $i$, the clique contains the edge $c_{x_i}{c}_{y_i}$. Concatenatinggives an $x_i$-$y_i$ path in a graph. The linkage paths are mutually vertex-disjoint, their clique endpoints are all distinct, and the joining clique edges pair those endpoints without introducing a new vertex. The resulting paths $P_1,\dots ,P_k$ are therefore mutually vertex-disjoint. In particular, under the stated clique hypothesis, the $2k$-connected graph is $k$-linked for these terminals.

Graph paths are vertex-disjoint if no vertex belongs to more than one of them, including their endpoints. In contrast, internally vertex-disjoint paths between common endpoints are allowed to share exactly those endpoints. The Set version of Menger theorem uses vertex-disjointness, while the two-terminal form uses internal vertex-disjointness.