Paths and edge-connectivity in graphs (Q799691): Difference between revisions

Let \((s_ 1,t_ 1),...,(s_ k,t_ k)\) be pairs of vertices of a finite graph G. Which conditions G has to fulfill such that there exist edge-disjoint paths \(P_ 1,...,P_ k\) with ends \(s_ i\), \(t_ i\) of \(P_ i\) (1\(\leq i\leq k)?\) This question has been considered by many authors. In this article sufficient conditions for \((\{s_ 1,...,s_ k,t_ 1,...,t_ k\}|\in \{3,4,5\}\) are given. For the case 3 see also \textit{P. D. Seymour} [Discrete Math. 29, 293-309 (1980; Zbl 0457.05043)]. Also a generalization of the following unpublished result of Mader is proved: For every k-edge-connected graph G (\(k\geq 4)\), there exists a path joining two given vertices such that the subgraph obtained from G by deleting the edges of the path is (k-2)-edge-connected.