Expanding Graphs Contain All Small Trees
The assertion of the title is formulated and proved. The result is then used to construct graphs with a linear number of edges that, even after the deletion of almost all of their edges or almost all of their vertices, continue to contain all small trees.
© 1987 Springer-Verlag
Friedman, J. and Pippenger, N. "Expanding Graphs Contain All Small Trees", Combinatorica, 7 (1987), 71-76. doi: 10.1007/BF02579202