An improved upper bound on the maximum degree of terminal-pairable complete graphs

Abstract A graph G is terminal-pairable with respect to a demand (loopless) multigraph D on the same vertex set as G , if there exist edge-disjoint paths joining the end vertices of every demand edge of D . In this short note, we improve the upper bound on the largest Δ ( n ) with the property that the complete graph on n vertices is terminal-pairable with respect to any demand multigraph of maximum degree at most Δ ( n ) . This disproves a conjecture originally stated by Csaba, Faudree, Gyarfas, Lehel and Schelp.