Bounds on path connectivity (Q761468)

A graph is k-path-connected if it has at least 2k vertices and, for any k pairs of distinct vertices, there are k disjoint paths connecting them. The authors prove a result implying the existence of a function f(d) such that no planar graph of maximum degree d is f(d)-path-connected. For edge-connectivity the following interpolation theorem is proved: Let \(s_ 1,t_ 1,s_ 2,t_ 2\) be vertices such that, for each \(i=1,2\), there are k edge-disjoint paths between \(s_ i\) and \(t_ i\) and let m be any natural number less than k. Then the graph contains a collection of m edge-disjoint paths such that m or \(m+1\) of these connect \(s_ 1\) and \(t_ 1\) and the others connect \(s_ 2\) and \(t_ 2\).