Disjoint paths in graphs. (Reprint) (Q2497998)

Reprint of an important article published in Discrete Math. 29, 293--309 (1980; Zbl 0457.05043). Generalizations of both edge (and vertex) versions of Menger's theorem on the number of edge disjoint (vertex disjoint) paths between a pair of vertices of a graph are proved. Let \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\) be \(k\) pairs of vertices of a graph \(G\). Necessary and sufficient conditions for the existence of edge disjoint (vertex disjoint) paths between \(x_i\) and \(y_i\) for \(1 \leq i \leq k\) are proved when either \(k = 2\) or when \(| \{x_1, y_1, x_2, y_2, \dots, x_k, y_k\}| = 3\).