A Variation of the Erdős–Sós Conjecture in Bipartite Graphs

The Erdős–Sós Conjecture states that every graph with average degree more than k- 2 contains all trees of order k as subgraphs. In this paper, we consider a variation of the above conjecture: studying the maximum size of an (n, m)-bipartite graph which does not contain all (k, l)-bipartite trees for given integers n≥ m and k≥ l. In particular, we determine that the maximum size of an (n, m)-bipartite graph which does not contain all (n, m)-bipartite trees as subgraphs (or all (k, 2)-bipartite trees as subgraphs, respectively). Furthermore, all these extremal graphs are characterized.