= Solution
{c}
\b[No.] A counterexample works for every $k\geq2$. Take the <complete bipartite graph> $G=K_{k,k}$ with <vertex sets>
$$
A=\{a_1,\ldots,a_k\},\qquad B=\{b_1,\ldots,b_k\}.
$$
It 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>.
Choose
$$
U=\{b_1,a_1,\ldots,a_{k-1}\},\qquad
W=\{b_2,\ldots,b_k,a_k\},
$$
and 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_1b_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.
Back to article page
