Menger’s Theorem and Short Paths

Abstract

For positive integers $d$ and $m$, let ${\text{P}}_{\text{d,m}}(\text{G})$ denote the property that between each pair of vertices of the graph $G$, there are m vertex disjoint (except for the endvertices) paths each of length at most $d$. Minimal conditions involving various combinations of the connectivity, minimal degree, edge density, and size of a graph $G$ to insure that ${\text{P}}_{\text{d,m}}(\text{G})$ is satisfied are investigated. For example, if a graph $G$ of order n has connectivity exceeding $(\text{n-m})/\text{d + m}–1$, then ${\text{P}}_{\text{d,m}}(\text{G})$ is satisfied. This result is the best possible in that there is a graph which has connectivity $(\text{n-m})/\text{d + m}–1$ that does not satisfy ${\text{P}}_{\text{d,m}}(\text{G})$. Also, if an $m$-connected graph $G$ of order $n$ has minimal degree at least $\lfloor (\text{n – m}+2)/\lfloor (\text{d}+4)/3\rfloor \rfloor +\text{m}-2$, then $G$ satisfies ${\text{P}}_{\text{d,m}}(\text{G})$. Examples are given that show that this minimum degree requirement has the correct order of magnitude, and cannot be substantially weakened without losing Property ${\text{P}}_{\text{d,m}}$.