Tree embeddings (Q2712588)

Suppose that \(T\) is a tree with \(t\) edges. As a consequence of the main result of the paper, it is proved that if a graph \(G\) has average degree \(> t-1\) and does not contain a copy of \(K_{2,r} \) for \(r = \lfloor {t/18}\rfloor \), then \(G\) must contain a copy of \(T\). The proof gives a polynomial time algorithm for finding a copy of \(T\) in \(G\). The value of \(r\) is not claimed to be best possible.NEWLINENEWLINENEWLINEThe Erdős-Sos conjecture says that one should be able to eliminate the hypothesis that \(G\) does not contain a copy of \(K_{2,r} \).