Discrete Math Seminar

The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac{n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree …