A Generalization of the Graph Packing Theorems of Sauer-Spencer and Brandt

Abstract

We prove a common generalization of the celebrated Sauer-Spencer packing theorem and a theorem of Brandt concerning finding a copy of a tree inside a graph. This proof leads to the characterization of the extremal graphs in the case of Brandt's theorem: If $G$ is a graph and $F$ is a forest, both on $n$ vertices, and $3\Delta (G)+{\ell }^{\ast }(F)\le n$, then $G$ and $F$ pack unless $n$ is even, $G=\frac{n}{2}{K}_2$ and $F=K_{1,n-1}$; where ${\ell }^{\ast }(F)$ is the difference between the number of leaves and twice the number of nontrivial components of $F$.