On Subtrees of Directed Graphs with No Path of Length Exceeding One
Ron L. Graham · Canadian Mathematical Bulletin · 1970
The following theorem was conjectured to hold by P. Erdös [1]: Theorem 1. For each finite directed tree T with no directed path of length 2, there exists a constant c(T) such that if G is any directed graph with n vertices and at least c(T)n edges and n is sufficiently large, then T is a subgraph of G. In this note we give a proof of this conjecture. In order to prove Theorem 1, we first need to establish the following weaker result.