The Erdös-Sós conjecture for graphs of girth 5 (Q1916132): Difference between revisions

In [Extremal problems in graph theory, Theory Graphs Appl., Proc. Sympos. Smolenice 1963, 29-36 (1964; Zbl 0161.20501)] \textit{P. Erdös} stated two conjectures due to Vera T. Sós and himself: that every graph on \(n\) vertices and \(\lfloor {1\over 2} (k- 1)n\rfloor+ 1\) edges contains all trees having exactly \(k\) edges; and that every graph on \(n\) vertices and \[ \max\left\{\left(\begin{smallmatrix} 2k- 1\\ 2\end{smallmatrix}\right)+ 1, (k- 1) n- (k- 1)^2+ \left(\begin{smallmatrix} k- 1\\ 2\end{smallmatrix}\right)+ 1\right\}\text{ edges} \] contains all forests having exactly \(k\) edges. The authors report that the conjecture for forests ``was verified by the first author in [Subtrees and subforests of graphs, J. Comb. Theory, Ser. B 61, No. 1, 63-70 (1994; Zbl 0804.05024)]. Since a complete solution (of the conjecture for trees) seems to be out of reach, partial solutions might be interesting. We prove that (this) conjecture is true for graphs without cycles of lengths 3 and 4''. In a note added in proof they report on recent work of J.-F. Saclé and M. Wozniak, who, in particular, proved the tree conjecture for graphs without cycles of length 4.