Let $k\in\mathbb N$. Given a finite graph with two subsets of vertices $X$ and $Y$, Menger's Theorem gives a criterion for when there are $k$ pairwise disjoint paths starting in $X$ and ending in $Y$.


Now let $X\_1$, $Y\_1$, $\dots$,$X\_k$, $Y\_k$ be subsets of vertices. Is there a "similar" condition for when there are $k$ pairwise disjoint paths, one path starting in $X\_1$ and ending in $Y\_1$, a second path starting in $X\_2$ and ending in $Y\_2$, $\dots$, and a $k^{\text {th}}$ path starting in $X\_k$ and ending in $Y\_k$?



Menger's theorem with restrictions on where the paths can begin and end
There is no known necessary and sufficient condition like in Menger's theorem.


However, there is a polynomial-time algorithm that decides if the paths exist. This is one of the main results of the Graph Minors Project of Robertson and Seymour (see [Graph Minors XIII](https://www.sciencedirect.com/science/article/pii/S0095895685710064)). The algorithm is quite involved and uses many of the results from the graph minors series. Robertson and Seymour solve the problem when each $X\_i$ and $Y\_i$ have size $1$, but your problem can be reduced to this case by shrinking each $X\_i$ and each $Y\_i$ to a single vertex.


The $k=2$ case (with $|X\_1|=|X\_2|=|Y\_1|=|Y\_2|=1$) has a nice necessary and sufficient condition for $4$-connected graphs. The required paths do not exist if and only if $G$ is planar and $X\_1, X\_2, Y\_1, Y\_2$ occur in this cyclic order on the outerface of $G$. This was proved independently by Thomassen and Seymour.


No necessary and sufficient conditions are known for $k \geq 3$.


