Expanding graphs contain all small trees (Q1092058): Difference between revisions

Let N(S) denote the set of neighbors of the vertices in set S. Then the authors prove if G is a non-empty graph such that for every set S with at least 2n-2 vertices, \(| N(S)| \geq (d+1)| S|\), then G contains every tree with n vertices and maximum degree at most d. Moreover, for fixed d and any real number \(0<s<1\), then for every n there exists a graph G with O(n) edges such that every subgraph with fraction s of G's edges contains every tree with n vertices and maximum degree at most d.