Past exam of the graph theory course of the University of Oxford / 2023 / 3 / c / ii / Solution

No. A counterexample works for every $k\ge 2$. Take the complete bipartite graph $G=K_{k,k}$ with vertex setsIt is a k-connected graph: deleting fewer than $k$ vertices leaves at least one vertex in each side, and the remaining complete bipartite graph is a connected graph.

Chooseand order these sets so that $u_1=b_1$ and $w_1=b_2$. Order the other members arbitrarily. These are disjoint sets of cardinality $k$, and every vertex of $G$ is one of the specified endpoints.

If the prescribed $k$ vertex-disjoint paths existed, no one of them could have an internal vertex, because every vertex must serve as the endpoint of one of the graph paths. Thus each graph path would have to be a single edge. But $b_1,b_2$ lie in the same side of the bipartite graph, so there is no edge $b_1{b}_2$. This contradicts the requirement on $P_1$.

For $k=2$ this is the four-vertex cycle graph, with opposite vertices paired. The stronger property that every prescribed pairing can be realized is the linked graph property; vertex connectivity alone does not guarantee it.