Expanding graphs contain all small trees

Abstract

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 Akadémiai Kiadó.