Menger’s Theorem and Short Paths

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}}\).