Bipartite Version of the Erd\H{o}s-S\'{o}s Conjecture

Abstract:

      The Erd\H{o}s-S\'{o}s Conjecture states that every graph on $n$ vertices and more than $\frac{n(k-2)}{2}$ edges contains every tree of order $k$ as a subgraph. In this note, we study a weak (bipartite) version of Erd\H{o}s-S\'{o}s Conjecture. Based on a basic lemma, we show that every bipartite graph on $n$ vertices and more than $\frac{n(k-2)}{2}$ edges contains the following families of trees of order $k$: (1) trees of diameter at most five; (2) trees with maximum degree at least $\lfloor \frac{k-1}{2}\rfloor$; (3) almost balanced trees, these results are better than the corresponding known results for the general version of the Erd\H{o}s-S\'{o}s Conjecture.