Paths and edge-connectivity in graphs. III: Six-terminal k paths (Q1101467): Difference between revisions

[For part II see the author's paper in Number Theory and Combinatorics, Proc. Conf. Tokyo/Jap., Okayama/Jap. and Kyoto/Jap. 1984, 337-352 (1985; Zbl 0613.05036).] As in part I [J. Comb. Theory, Ser. B 37, 151-172 (1984; Zbl 0548.05039)], the author studies the existence in graphs of edge-disjoint paths which have given ends. Let \(k\geq 1\) be an odd integer and \((s_ i,t_ i)\), \(1\leq i\leq k\), be pairs of vertices of a graph G. The author proves that if the number of considered vertices \(s_ 1,...,s_ k,t_ 1,...,t_ k\) is at most 6 and if the maximal number of edge-disjoint paths between each given pair of vertices \((s_ i,t_ i)\) (1\(\leq i\leq k)\) is at least k, then there exist k disjoint paths \(P_ 1,...,P_ k\) such that \(P_ i\) is a path between \(s_ i\) and \(t_ i\) (1\(\leq i\leq k)\).