EDGE-DISJOINT PATHS AND CYCLES IN N-EDGE-CONNECTED GRAPHS

We consider finite undirected loopless graphs G in which multiple edges are possible. For integers k, l greater-than-or-equal-to 0 let g(k, l) be the minimal n greater-than-or-equal-to 0 with the following property: If G is an n-edge-connected graph, s1,..., s(k), t1,..., t(k) are vertices of G, and f1,..., f(l), g1,..., g(l) are pairwise distinct edges of G, then for each i = 1,..., k there exists a path P(i) in G connecting s(i) and t(i) and for each i = 1,..., l there exists a cycle C(i) in G containing f(i) and g(i) such that P1,..., P(k), C1,..., C(l) are pairwise edge-disjoint. We give upper and lower bounds for g(k, l).