On an Induced Version of Menger's Theorem

Abstract

We prove Menger-type results in which the obtained paths are pairwise nonadjacent, 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 exist either k pairwise non-adjacent X-Y-paths, or a set of fewer than Ck vertices which separates X and Y. We further show better bounds in the sub cubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.