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 multigraph $D$ on the same vertex set as $G$, if there exists 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 $\Delta (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 $\Delta (n)$. This disproves a conjecture originally stated by Csaba, Faudree, Gyárfás, Lehel and Schelp.

4 pages