### Abstract

Suppose that (s_{1}, t_{1}),...,(s_{k}, t_{k}) are pairs of vertices of a graph. When can one choose a path between s_{1} and t_{1} for each i, all pairwise edge-disjoint? Menger's theorem answers this when s_{1},...,s_{k}, t_{1},...,t_{k} take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases. 1. (i) when k = 2, and 2. (ii) when s_{1},...,s_{k}, t_{1},...,t_{k} 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.

Original language | English (US) |
---|---|

Pages (from-to) | 293-309 |

Number of pages | 17 |

Journal | Discrete Mathematics |

Volume | 29 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1980 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Disjoint paths in graphs'. Together they form a unique fingerprint.

## Cite this

Seymour, P. D. (1980). Disjoint paths in graphs.

*Discrete Mathematics*,*29*(3), 293-309. https://doi.org/10.1016/0012-365X(80)90158-2