Subtrees and subforests of graphs (Q1328385)

Let \(G\) be a finite, simple graph. Let \(| G |\), \(e(G)\), \(\Delta (G)\), and \(\delta (G)\) denote respectively the order, size, maximum degree, and minimum degree of \(G\). For two positive integers \(k\) and \(n\) \((>k)\) set \[ f(k,n) = \max \left\{{2k - 1 \choose 2}, {k - 1 \choose 2} + (k - 1) (n - k + 1) \right\}. \] A graph \(G\) is said to contain a graph \(H\) if \(H\) can be embedded in \(G\), i.e. \(G\) contains a subgraph isomorphic with \(H\). The author gives elegant proofs to the following two theorems. Theorem 1. Suppose \(G\) is a graph of size \(e(G) > f(k,n)\). Then \(G\) contains every forest on \(k\) edges without isolated vertices. Theorem 2. Let \(r\) be a positive integer. Suppose \(G\) is a graph of order \(n \geq r^ 2 - r + 1\) with \(\Delta (G) = n - 1\) and \(\delta (G) \geq n - r\). Then \(G\) contains all trees of order \(| G |\). Theorem 1 answers a long-standing conjecture (posed in 1963) of Erdős and Sòs in the affirmative. Theorem 2 improves a result due to \textit{R. J. Faudreee}, \textit{C. C. Rousseau}, \textit{R. H. Schelp} and \textit{S. Schuster} [Isr. J. Math. 35, 177-185 (1980; Zbl 0436.05020)].