Cambalache 3,14 - La vidriera irrespetuosa

The Erdös-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k − 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ξ(G) of a graph G defined as ξ(G) = min{d(u) + d(v) − 2 : uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree ∆(G) ≥ k and minimum edge degree ξ(G) ≥ 2k − 4 contains every tree of k edges if dG (x) + dG (y) ≥ 2k − 4 for all pair x, y of nonadjacent neighbors of a vertex u of dG (u) ≥ k.