A variant of the Erdős‐Sós conjecture. Issue 1 (8th November 2019) - Havet, Frédéric; Reed, Bruce; Stein, Maya; Wood, David R.
Abstract: A well‐known conjecture of Erdős and Sós states that every graph with average degree exceeding m − 1 contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least ⌊ 2 m / 3 ⌋ contains every tree with m edges. As evidence for our conjecture we show (a) for every m there is a g ( m ) such that the weakening of the conjecture obtained by replacing the first m by g ( m ) holds, and (b) there is a γ > 0 such that the weakening of the conjecture obtained by replacing ⌊ 2 m / 3 ⌋ by ( 1 − γ ) m holds.