On an Induced Version of Menger's Theorem

Abstract

We prove Menger-type results in which the obtained paths are pairwise non-adjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topological minor. More precisely, we show the existence of a constant $C$, depending only on the maximum degree or on the forbidden topological minor, such that for any pair of sets of vertices $X,Y$ and any positive integer $k$, there exists either $k$ pairwise non-adjacent $X\text{-}Y$-paths, or a set of fewer than $Ck$ vertices which separates $X$ and $Y$. We further show better bounds in the subcubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.