Strengthening of Menger's Theorem Is there a proof or counterexample for the following strengthening of Menger's Theorem? Let $G$ be a $k$-connected graph. For some $x,y \in V(G)$, let $P_1, \ldots, P_{k-1}$ be $k-1$ internally disjoint paths from $x$ to $y$. Is there necessarily a $k$th path $P_k$ from $x$ to $y$ which is internally disjoint from $P_1, \ldots, P_{k-1}$? Note: Menger's Theorem only says there are $k$ internally disjoint paths from $x$ to $y$. My question is this: Can you extend any collection of $k-1$ internally disjoint paths into a collection of $k$ internally disjoint paths?

No; one way this can become impossible is if the first $k-1$ paths "use up" all the vertices that a $k^{\text{th}}$ path would need to use. For example:

![enter image description here](

This graph is $2$-connected, and there are $2$ internally disjoint paths from the left vertex to the right vertex. But if you start with the path highlighted in red, then you can't find a second path internally disjoint from the red path.