Cohesion and Non-Separating Trees in Connected Graphs

Abstract

If $T$ is a tree on $n$ vertices, $n\ge 3$, and if $G$ is a connected graph such that $d(u)+d(v)+d(u,v)\ge 2n$ for every pair of distinct vertices of $G$, it has been conjectured that $G$ must have a non-separating copy of $T$. In this note, we prove this result for the special case in which $d(u)+d(v)+d(u,v)\ge 2n+2$ for every pair of distinct vertices of $G$, and improve this slightly for trees of diameter at least four and for some trees of diameter three.