Disjoint paths in graphs

Suppose that (s1,t1),…,(sk,tk)(s1,t1),…,(sk,tk) are pairs of vertices of a graph. When can one choose a path between sisi and titi for each i  , all pairwise edge-disjoint? Menger's theorem answers this when s1,…,sk,t1,…,tk take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases,(i) when k=2k=2, and(ii) when s1,…,sk,t1,…,tk take only three distinct values—the solution to this is obtained by applying a theorem of Mader.We obtain both good characterizations and good algorithms for these problems. The analogous “vertex-disjoint” problems are also solved.