Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 17H / d / Solution

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.

Solved by gpt-5.6-sol high.